Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
I take it that products and square roots are out? Otherwise, you could use Heron's formula. –  Lee Mosher Feb 16 '13 at 15:26
    
On the other hand, general weighted graphs cannot all be realized by quadrilaterals in the Euclidean plane: the triangle inequality might not hold; and even if it does, not all 4 point metric spaces embed in the plane. –  Lee Mosher Feb 16 '13 at 16:23
    
@Günter: sorry that I wasn't precise enough - actually the question concerns a weighted complete graph, with 4 vertices that represent distinct points points $A$,$B$,$C$ and, $D$ of the euclidean plane and the weights $w$ of edges that represent the euclidean distances $a=w(A,B)$,$b=w(B,C)$,$c=w(C,D)$,$d=w(D,A)$,$e=w(A,C)$,$f=w(B,D)$ between the points. Is there a system of l(in-)equalities, linear in $a$,$b$,$c$,$d$,$e$ and $f$, from which it is possible to determine whether the convex hull of the point set has four corners (i.e. points that are not convex combinations of other points)? –  Manfred Weis Feb 17 '13 at 15:13
    
@Günter: I will do the editing next weekend –  Manfred Weis Feb 18 '13 at 4:44

5 Answers 5

up vote 2 down vote accepted

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.

share|improve this answer
    
@Günter: maybe the answer lies in a case study of the linear factors of your degree-2 polynomials. –  Manfred Weis Feb 18 '13 at 4:32

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.

share|improve this answer
    
I wonder what the phrase "plus their adjacency relations" in the problem statement should mean. If if means that we know which of the distances represent edges, and which represent diagonals, then this example does not work. –  Günter Rote Feb 17 '13 at 13:06
    
@günter: it follows from the triangle inequality, that the pair of edges that constitutes to the maximal matching corresponds to the diagonals of a convex quadrilateral. So the problem is not to determine the diagonals, but rather whether they intersect each other. –  Manfred Weis Feb 17 '13 at 16:03

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.
            alt text

share|improve this answer
    
@Günter: I think you had your labels scrambled? I tried to fix them. Apologies if I altered your intention! Feel free to undo my changes. –  Joseph O'Rourke Feb 17 '13 at 1:39
    
This is a very minimal (hence elegant) argument. But if additions and sums allow repetitions (i.e. we need to consider linear combinations with arbitrary integer coefficients--which is here equivalent to rational coefficients) then I wonder if additional work is needed; at least I don't see a full proof immediately. –  Wlodzimierz Holsztynski Feb 17 '13 at 5:19
    
I interpreted the OP's wording differently: since the value of the diagonal BD itself has changed, then you can distinguish these three examples by the sum/difference expression "BD", in which the sum and the difference sign each appear zero times. Perhaps the OP can give us some guidance on what intepretation was intended. –  Lee Mosher Feb 17 '13 at 14:25
    
Lee, author's guidance is a possibility. Another is that once the question is out in public, and it's not exact, then the readers create the most tasty, juicy, fruitful, ... interpretations, open to doing mathematics. This latter was the case--of leaving room for interpretations--even with some of the famous Hilbert problems, hey! :-) So, it's a bit like in poetry. --* The author dies at the delivery of their poem. –  Wlodzimierz Holsztynski Feb 17 '13 at 19:30
    
@Lee, I don't get what you mean. By comparing sums or differences I understand something like $AB < AC-BD$. The OP does not talk about comparing the length $BD$ to the length $BD$ of another instance. –  Günter Rote Feb 17 '13 at 19:52

@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).

share|improve this answer
    
@Wlodzimierz: I do not doubt you, but could you please provide an example? –  Joseph O'Rourke Feb 17 '13 at 1:07
    
It's an obligation to have doubts :-) I need to think more about this question. Sorry for a false start. –  Wlodzimierz Holsztynski Feb 17 '13 at 2:12
    
I think that I have an example of a convex, symmetric trapezoid, which has the six lengths the same as a not convex, symmetric quadrilateral, with two long sides of the same length as the diagonals of the trapezoid; and the six distances &nbsp; (δ δ a A b b) in each case are the same--there are 4 different distances, since there are two pairs of equal (symmetric) distances. * If I manage, I'll provide the details a bit later. –  Wlodzimierz Holsztynski Feb 17 '13 at 4:09
    
My question also includes that the adjacency relation between sides (i.e. which triplets of distances correspond to adjacent edges) are given. It is fairly easy to determine convexity from triangle's areas (which can be calculated from side-lengths via the Heronic formula): if the area of the largest triangle equals the sum of the areas of the remaining ones, then the quadrilateral isn't convex. Concerning the triangulation of complete metric graphs, one might resort to triangle areas to decide whether two non-adjacent edges intersect. –  Manfred Weis Feb 17 '13 at 10:14

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.

alt text

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.

share|improve this answer
    
A reconstruction of a set of 4 points $A$,$B$,$C$ and $D$, whose distance equal the given $AB$,$BC$,$CD$,$DA$,$AC$ and $BD$ is fairly easy: construct triangle $ABC$ from the given lengths, then construct the intersection point of a circle around $A$ with radius $AD$ and around $B$ with radius $BD$ and chose as $D$ the intersection point, whose distance from $C$ equals $CD$; but how does it help to determine without visual inspection, whether the convex hull of $A$,$B$,$C$ and $D$ has four corners and, apart from that, circles are quadratic algebraic curves. –  Manfred Weis Feb 24 '13 at 12:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.