Characterizing Convex Configurations of Quadrupels of Coplanar Points via Linear (In-)equalities between Distance Sums or Differences

Question

Given 4 points $A$, $B$, $C$ and $D$ in general position in the euclidean plane, is it possible to determine from the 6 distances $AB$, $BC$, $CD$, $AD$, $AC$ and, $BD$ alone, whether every point is a corner of their convex hull under the restriction that comparing sums and/or differences of the distances is the only allowed operation and that no information about the point's coordinates is available.

Background of the question is whether it is possible to generalize the concept of intersection to non-adjacent edges of a general weighted graph. If the answer were affirmative, then geometric concepts like inside/outside relations or convex hulls would be an "intrinsic" property of graphs; triangulations of complete graphs would then also be more flexible and could contain complete subgraphs of order 4.

Answer 1

Here is a sketch of an answer that involves the squared Euclidean distances between the four points $A,B,C,D$ (and only the squared ones, not a mixture between squared and non-squared distances.)

Suppose $D$ is the origin, and consider the vectors $a=DA, b=DB, c=DC$. From $$AB^2 = \langle a-b,a-b \rangle = DA^2 -2\langle a,b\rangle + DB^2,$$ we get $\langle a,b\rangle$ as a linear expression in terms of the squared distances, and similarly for the other mixed inner products. The inner "self"-products like $\langle a,a\rangle=DA^2$ are directly available anyway. Assuming that $a$ and $b$ are linearly independent, we can write $$c=\lambda a + \mu b.\ \ \ \ \ (1)$$ Then $D$ (the origin) is in the convex hull of $A,B,C$ iff $\lambda\le 0$ and $\mu \le 0$. Multiplying (1) by $a$, $b$, and $c$ gives an overdetermined system of three equations $$\langle a,c\rangle = \lambda\langle a,a\rangle+\mu\langle a,b\rangle,$$ etc. from which an expression (actually, three equivalent expressions) for $\lambda$ and $\mu$ can be derived using Cramer's rule, as a quotient of determinants. Hence, the sign of these determinants tells us if $D$ is a vertex of the convex hull or not.

So in the end it boils down to $2\times 2$ determinants whose entries are linear in the squared distances, i.e., degree-2 polynomials in the squared distances. One would have to work out what these expressions are. Who knows, maybe a clever combination of the various redundant expression gives even linear expressions, or expressions that can be factorized into nice linear terms.

Answer 2

EXAMPLE   Consider points in   $R^2$:

• $A := (-1\ \ 2)$
• $B := (1\ \ 2)$
• $C := (-2\ \ 4)$
• $D := (2\ \ 4)$

and another quadruple:

• $P := (0\ \ 0)$
• $Q := (0\ \ 2)$
• $S := (-2\ \ 3)$
• $T := (2\ \ 3)$

For each of these quadruples the six distances are the same, namely: $$2\quad 4\quad \sqrt 5\quad \sqrt 5\quad \sqrt{13}\quad \sqrt{13}$$

The convex hull of the first quadruple is a (non-degenerated) trapezoid, while the convex hull of the second one is a triangle, where one of the points is inside the triangle (in the topological interior). Thus the answer to epsilontik's question is negative: NO.

Answer 3

No. (This was an answer to a previous, not entirely clear version of the problem.) Take an equilateral triangle ABC of side length 1, plus the midpoint D of the side AC. By pushing D slightly in or out parallel to the line BC, you can make ABCD nonconvex or convex. BD is the only irrational distance among the 6 distances. By taking the perturbation sufficiently small (say $\pm0.01$), you cannot distinguish from sums and differences whether BD is larger or smaller than in the original (degenerate) position.
           

Answer 4

@epsilontik, I assume that you mean that just 6 positive reals are given (corresponding to the distances between certain 4 points of the Euclidean plane.

The answer is NO--such data cannot determine the convexity because the same 6 positive reals can stand for two completely different 4-point sets, where in one case none of the points belongs to the convex hall of the remaning three, while in the other case one will. After connecting these points, in each case separately, by straight intervals, the (non-intersecting) diagonals in the non-convex case will have lengths equal to the lengths of two of the sides in the other case.

---

I thought I see an example by continuously deforming one configuration into another, with an intermediate one giving a solution. Now I don't see it anymore, and even have serious doubts about it, sorry. (Please, remove the undeserved by me vote for my premature answer :-)). Sorry. (I'll patiently use paper and pen next time, for verification, before rushing my happy announcement).

Answer 5

As nicely shown above, If we merely have a set of six distances the answer is no. Rearranging that example we see that it remains no even if we are given that the points all have integer coordinates and we know the individual lengths $AB,AC,BC,AD$ but we have the two values $BC,BD$ without knowing which is which.

Given the six lengths and the full ability to do geometric constructions or algebra we can locate $D.$ Knowing $AB,AC,BC$ along with $BD$ and $CD$ limits $D$ to one of two locations which are not equally distant from $A$. Sometime the answer would be obvious such as $AD=BD=CD$ and $AB=AC=BC.$ I think that if we could go off and do calculations we could come back and know what additions and comparisons to do to answer the question. However a simple algorithm seems unlikely to me because it could depend on very minute differences.

As an easy case (again adapted from another answer): suppose we know that $AB=BC=AC$ and I next tell you " $BD=CD$ and they are both just slightly over $\frac{AC}{2}$" You might say (to yourself) " ok, the exact value doesn't matter , I just need to determine if $AD$ is more or less than $\frac{\sqrt{3}AC}{2}.$" If you are just adding, subtracting and comparing your given values then there are various rationals you can use as test cases. $6/7 \lt 84/97 \lt 1170/1351, \lt 16296/18817\lt \cdots \lt \frac{\sqrt{3}}{2}$ Also $ \frac{\sqrt{3}}{2} \lt \cdots \lt 35113/40545 \lt 2521/2911 \lt 181/209 \lt 13/15 \lt 1$ so if $97\ AD \le 84\ AC$ the point is surely inside and if $181\ AC \le 209\ AD$ it is surely outside but otherwise you don't know yet. If you go back and get the actual value of $BD=CD$ then that will tell you the accuracy you need. Say that $BD=(1/2+\epsilon)AC$ then $AD=\frac{AC\sqrt{3}}{2} \pm AC\sqrt{\epsilon+\epsilon^2}$ so an accuracy of $\epsilon AC$ will be quite sufficient. But how to translate that into a simple procedure is not that clear.

Answer 6

One sufficient condition for convexity is, that the edges of the maximum-weight perfect matching are the two edges of maximal weight.

Proof:

• assume that $A,B,C,D$ are four points in non-convex general position in the euclidean
  plane,

• assume further that $a:=\{A,B\}; b:=\{B,C\}; c:=\{C,D\};$
  $d:=\{D,A\}; e:=\{A,C\}; f:=\{B,D\};$
  w.l.ö.g
  $a,b,c,d\ < e,f$
  $a+c,\ b+d\ < e+f$
  $a+f+d,\ b+c+f,\ e+c+d\ <\ a+b+c$
  and, assume that $D$ is inside $\Delta_{ABC}$

• clearly, $e$ is one of the sides of $\Delta_{ABC}$ and, because $e$ and $f$ constitute to a matching, $f$ must be ajacent to the $3rd$ corner of $\Delta_{ABC}$ and, because $f$ is longer than the two adjacent triangle-sides and, because $D$ is adjacent to $f$, but no corner of $\Delta_{ABC}$, it follows, that $D$ is outside $\Delta_{ABC}$ and consequently, that $A,B,C,D$ are in convex configuration contrary to the assumption.