1
$\begingroup$

Is the following conjecture correct?

Conjecture:

If $A,B,C,D$ are four points in general position in the euclidean plane, with

$a:=\|C-B\|,\ \ b:=\|C-A\|,\ \ c:=\|B-A\|$
$a':=\|D-A\|,\ b':=\|D-B\|,\ c':=\|D-C\|$ ,

$\begin{align} a+b+c\ &>\ a+b'+c',\ a'+b+c',\ a'+b'+c\\ c+c'\ &>\ a+a',\ b+b'\\ \end{align} $,

then $A,B,C,D$ are in strict convex configuration iff $$(a'+b')((a+c')(a-c')-a'b')+b'(b+a)(b-a) \ \lt 0$$

If so, then checking planar convexity of four points is possible with 6 length measurements and 5 multiplications. This checks convexity via an inequality, so it is stable under small displacements of the points into 3-space.

By contrast, using the equality

$$area(ABC) + area(ACD) = area(ABD) + area(BCD)$$

in a check of convexity, which also can be done with only six length measurements, makes the check unstable under those small displacements. The first approach is based on Stewart's Theorem, where the lengths $a',b',c'$ are known as $d,m,n$; the second approach is based on Heron's Formula instead.


Addendum:

A week has passed, since I asked for the correctness of checking planar convexity with Stewart's formula without any reply in that respect.

I will therefore provide the requested "justification" and motivation for checking planar convexity by means of distances albeit that task seems simple in coordinate geometry.

The first remark in that respect is a word of warning when checking convexity via sums of triangle areas.

If the triangles aren't carefully choosen, one might get false results even with planar coordinates and $3\times 3$ determinants in the standard way as described by David Eppstein:
Suppose you are given 4 points $A, B, C, D$ in general position in the Euclidean plane and, from those you calculate the triangle areas $ABC,ABD,BCD,ACD$; how do you then pair up the triangles to get a correct convexity check? As it turns out, it may be necessary to make three checks for equality of sum of pairs of triangle areas. In contrast, it suffices to check whether the sum of the three smallest areas exceeds the largest area, in which case the points are definitely in strict convex configuration.

Now consider the case where $A, B, C, D$ are in general configuration in a hyperplane of $E^n$; in that case the computational effort increases with the dimension of space. Another problem with point-coordinates is that they need not necessarily be cartesian, e.g. GPS coordinates, whence you have to convert them to 3D cartesian coordinates only to be able to calculate the triangle areas you need to know.
If in contrast the 6 distances between the pairs of points have been measured, deciding about the planar convexity of the point's configuration via Stewart's formula would seem much easier (provided its correctness, which isn't confirmed yet).

And, not to forget that coordinates are no physical entities whereas distances are; so, albeit coordinates are very convenient, they are not the basis of euclidean geometry and therefore IMHO it should be beneficial to investigate distance-geometric algorithms and their inherent complexity.
A further argument in favor of distance based geometric definitions is that they can be used directly in more general settings like on manifolds or discrete structures.

That said, I am astonished that that aspect of my question apparently hasn't played a role in the replies I got so far.

$\endgroup$
  • 3
    $\begingroup$ The standard method for checking this is to compare the signs of the four $3\times 3$ determinants whose rows are $(x_i,y_i,1)$. As with your proposed test, this involves inequality rather than equality. It will also detect collinearities (if any of the determinants is zero) and does not require the coordinates or their linear combinations to be sorted. Additionally, because it involves only quadratic polynomials in the coordinates (not cubics in square roots of quadratic combinations of coordinates as in your proposed test) it can be computed accurately using lower numerical precision. $\endgroup$ – David Eppstein Sep 16 '18 at 20:53
  • $\begingroup$ @DavidEppstein your arguments are of course valid clarification if point coordinates are given; but still, if the four points are in deltoid configuration in the xy-plane, the sum of the areas of the 3 triangles with smallest circumference equals the area of the one with largest circumference; the same is true if the points are not in general position. If the points are in strict convex configuration, the sum of the three smallest triangle's areas exceeds the one of the largest triangles [continued in next comment...] $\endgroup$ – Manfred Weis Sep 17 '18 at 3:06
  • $\begingroup$ @DavidEppstein [...continued] and the same is true if the inner point of the deltoid configuration is displaced by an arbitrary small $\epsilon$ in z-direction. Another point is, that coordinates are not always initially available, e.g. in data from field survey or, if one attempts to port the notion of convexity to weighted complete and symmetric graphs. All in all checking convexity via Stewart's formula is just another plate on a Smörgåsbord of algorithms. $\endgroup$ – Manfred Weis Sep 17 '18 at 3:14
  • $\begingroup$ @ManfredWeis, it would help to edit the question to start with the field survey setup, clarify how the test via Heron’s formula works, and specify the notion of stability under small z-displacements. You can do all that without needing to make comments longer than the space allowed! $\endgroup$ – Matt F. Sep 17 '18 at 4:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.