How to prove that a point cannot lie within a triangle based on statements about triangles containing points.

Question

I'm a total newb and bottom rung hobbyist mathematician, just fair warning.

Say points a,b,c,d,e are in the plane (general position) and triangle abc contains point d, triangle ade contains point c. It seems intuitive that triangle bcd cannot contian point e, but I don't know how to prove it, without trying actual values for the coordinates. My first thought was to set up a system of inequalities, one for each statement of containment, similar to barrycentric coordinates (but using cross products), then somehow deduce a contradiction.

The inequality list looks like this. I gather one would have to check a number of different sign conditions, and perhaps all possible orderings of x and y. I'm ok to assume a specific ordering, like $a_x < e_x < c_x < d_x < b_x$ and $a_y < b_y < d_y < c_y < e_y$, if that helps. I already checked for simple sign conflicts (some orderings are easy to prove immediately via sign conflicts):

ABC contains D $$(d_x - a_x) (c_y - a_y) - (c_x - a_x) (d_y - a_y)>0$$ $$(d_x - b_x) (a_y - b_y) - (a_x - b_x) (d_y - b_y)>0$$ $$(d_x - c_x) (b_y - c_y) - (b_x - c_x) (d_y - c_y)>0$$

ADE contains C $$(c_x - a_x) (e_y - a_y) - (e_x - a_x) (c_y - a_y)>0$$ $$(c_x - d_x) (a_y - d_y) - (a_x - d_x) (c_y - d_y)>0$$ $$(c_x - e_x) (d_y - e_y) - (d_x - e_x) (c_y - e_y)>0$$

BCD contains E $$(e_x - b_x) (d_y - b_y) - (d_x - b_x) (e_y - b_y)>0$$ $$(e_x - c_x) (b_y - c_y) - (b_x - c_x) (e_y - c_y)>0$$ $$(e_x - d_x) (c_y - d_y) - (c_x - d_x) (e_y - d_y)>0$$

Can it be shown, just with the above statements, that the three "containment" statements cannot co-exist? I guess we also need to say that no three points are colinear and no two points are the same. Here's an example drawing, but of course I'm looking to prove this without assuming any particular configuration of the points. While a geometric reasoning proof would be interesting, my goal is to be able to programatically prove these sorts of statements, so analytical is best. I'm happy to improve the question with any feedback. thanks!

Answer 1

Suppose $A,B,C,D,E$ are points in the plane, no three of which are collinear, such that

• Triangle $ABC$ contains point $D$.$\\[4pt]$
• Triangle $ADE$ contains point $C$.

Claim:$\;$Triangle $BCD$ does not contain point $E$.

Proof:

Since $A,B,C$ are not collinear, there are unique real numbers $r,s,t$ with $r+s+t=1$ such that $$ D=rA+sB+tC\qquad(\text{eq}1) $$ Since $A,D,E$ are not collinear, there are unique real numbers $u,v,w$ with $u+v+w=1$ such that $$ C=uA+vD+wE\qquad(\text{eq}2) $$ Since $B,C,D$ are not collinear, there are unique real numbers $x,y,z$ with $x+y+z=1$ such that $$ E=xB+yC+zD\qquad(\text{eq}3) $$ Since $D$ is strictly contained in triangle $ABC$, it follows that $r,s,t > 0$, and since $C$ is strictly contained in triangle $ADE$, it follows that $u,v,w > 0$.

Computing $u{*}(\text{eq}1)-r{*}(\text{eq}2)$, and then solving the resulting equation for $E$, we get $$ E = \Bigl(\frac{us}{wr}\Bigr) B + \Bigl(\frac{ut}{wr}+\frac{1}{w}\Bigr) C + \Bigl(-\frac{u}{wr}-\frac{v}{w}\Bigr) D $$ Summing the coefficients of $B,C,D$, we get \begin{align*} & \Bigl(\frac{us}{wr}\Bigr) + \Bigl(\frac{ut}{wr}+\frac{1}{w}\Bigr) + \Bigl(-\frac{u}{wr}-\frac{v}{w}\Bigr) \\[4pt] =\;& \frac{r+us+ut-u-vr}{wr} \\[4pt] =\;& \frac{r-u(1-s-t)-vr}{wr} \\[4pt] =\;& \frac{r-ur-vr}{wr} \\[4pt] =\;& \frac{r(1-u-v)}{wr} \\[4pt] =\;& \frac{rw}{wr} \\[4pt] =\;& 1 \\[4pt] \end{align*} hence, from the uniqueness of $x,y,z$, it follows that $$ z=-\frac{u}{wr}-\frac{v}{w} $$ so $z < 0$, and therefore $E$ is not contained in triangle $BCD$.

Answer 2

One can give a geometrical proof by contradiction.

Suppose point $E$ lies inside triangle $BDC$. As all vertices of $BCD$ belong to $\angle BAC$, then all interior points of $BCD$ are also interior points of $\angle BAC$, and $E$ lies then inside $\angle BAC$, as $D$ does.

Hence $\angle AED$ is all inside $\angle BAC$ (with the exception of point $A$) and cannot contain point $C$, which contradicts a given hypothesis. It follows that $E$ doesn't lie inside $BDC$.

Answer 3

My method was by area: a point is inside a triangle if the $3$ triangle areas it creates (found via cross-product) add up to the total triangle areas: thus, $D$ and $C$ inside $ABC$ and $ADE$ respectively, imply

1. $$|AD\times AC|+|AB\times AD|+|BD\times CD|=|AB\times AC|$$
2. $$|AD\times AC|+|AC\times AE|+|DE\times CD|=|AD\times AE|$$ $$|AB\times AC|+|AC\times AE|+|DE\times CD|=|BD\times CD|+|AB\times AD|+|AD\times AE|$$

and is also clear from the construction of the triangles that both $C$ and $D$ lie in the triangle $AEB$. Edit: I fully justify this by considering the extension of the line $DE$ to where it intersects $AB$, and call this point $F$ [this point exists because it must cross two lines of the $ABC$ triangle and it doesn't cross $AC$ (note that $D$ can't lie on the line $AB$)]. So $AED$ is a proper subset of $AEF$. Making similar arguments, $AEF$ is a proper subset of $AEB$. So $C$ lies in $AEB$, and D as well. This implies that

3. $$|AB\times AD|+|AD\times AE|+|BD\times DE|=|AB\times AE|$$
4. $$|AB\times AC|+|AC\times AE|+|BC\times BE|=|AB\times AE|$$ $$|AB\times AD|+|AD\times AE|+|BD\times DE|=|AB\times AC|+|AC\times AE|+|BC\times BE|$$

hold as well. Suppose $E$ lay in $DBC$. Then

5. $$|BD\times DE|+|DE\times CD|+|BC\times BE|=|BD\times CD|$$

holds. But (1), (2), and (5) imply that

$$|AB\times AD|+|AD\times AE|+|BD\times DE|+|BC\times BE|=|AB\times AC|+|AC\times AE|$$

and (3) and (4) thus imply $$2|BC\times BE|=0$$ so we have achieved our contradiction.

Answer 4

I started working on this answer before the others were posted. It doesn’t add anything geometrically to their proofs, but it does relate them to your system of equations, and since you wrote that that’s your main focus, perhaps it will be relevant for you.

Each of your inequalities is a statement that three points form a clockwise triangle in a particular order. To simplify them, assume $a_x=a_y=0$ without loss of generality and let $PQ$ denote $|\vec P\times\vec Q|=p_xq_y-q_xp_y$, which is twice the oriented area of the triangle $PQA$ (so $QP=-PQ$). Then the system simplifies to

\begin{eqnarray} DC & > & 0 \;, \tag1 \\ BD & > & 0 \;, \tag2 \\ CD + DB + BC & > & 0 \;, \tag3 \\ \\ CE & > & 0 \;, \tag4 \\ DC & > & 0 \;, \tag5 \\ EC + CD + DE & > & 0 \;, \tag6 \\ \\ ED + DB + BE & > & 0 \;, \tag7 \\ EB + BC + CE & > & 0 \;, \tag8 \\ EC + CD + DE & > & 0 \;. \tag9 \end{eqnarray}

The first thing to note is that your choice of orientations is justified: You can choose the orientation of $ABC$ arbitrarily without loss of generality; then the consistency of $(1)$ and $(5)$ fixes the orientation of $ADE$, and then the consistency of $(6)$ and $(9)$ fixes the orientation of $BCD$.

Note also that for each containment, adding the three equations yields the equation for the orientation of the containing triangle (after cancellation of opposite terms), which corresponds to the addition of triangle areas in David Raveh’s answer.

Adding $(4)$ and $(5)$ to $(9)$ yields $DE>0$, and adding that and $(2)$ to $(7)$ yields $BE>0$. Together with $(1)$, $(2)$, $(4)$ and $(5)$, we thus have all $6$ equations that all pairs of points other than $A$ lie in the circular order around $A$ that they do in your diagram. We can simplify a bit further by introducing the corresponding six positive variables $p=BD$, $q=DC$, $r=CE$, $s=BC$, $t=DE$ and $u=BE$. The four equations that state more than the positivity of these variables then read

\begin{eqnarray} s & > & p + q \;, \tag{3'}\\ t & > & r + q \;, \tag{6'}\\ u & > & p + t \;, \tag{7'}\\ r + s & > & u \;. \tag{8'} \end{eqnarray}

I was hoping that this in itself would yield a contradiction, but it doesn’t; these inequalities can be satisfied with positive values of the variables, so we do need to use their definitions in terms of the $PQ$ to derive a contradiction.

At this point, having read the other answers, I realized that the circular order of the other points around $A$ derived above is actually all we need – if $B$, $D$, $C$ and $E$ lie around $A$ in that circular order, then $E$ can't lie in $BCD$.

One more thing you might want to take a look at: There are criteria for the planarity of a graph, that is, for when it’s possible to embed it in the plane such that none of its edges cross. One such criterion is that a plane graph cannot contain (a subdivision of) the complete graph on $5$ vertices, $K_5$. So if you can prove that your premises imply that none of the segments between pairs of points cross, that would yield a contradiction, since the diagram would then be an embedding of $K_5$ in the plane without crossings. This is easy for most of the potential crossings, since they’re excluded either by the triangle containments or by the circular order around $A$; but it’s not as easy for the potential crossing of $BC$ and $DE$ (the one actually realized in the diagram).