Given the coordinates of three points in the plane, what is the most computationally efficient way of determining whether a given fourth point is inside the triangle formed by the other three? If the triangle's vertices are P0, P1, and P2, and the fourth point is P3, we can place P0 at the origin by subtracting its coordinates from each of the others. Then compute a = x1 y2 - x2 y1 b = x1 y3 - x3 y1 c = x2 y3 - x3 y2 The point P3 is inside the triangle T{0,1,2} iff ab > 0 AND ac < 0 AND a(a-b+c) > 0 Also, one of the points is inside the triangle formed by the other three iff abc(a-b+c) < 0 This criterion is related to the note Parabola Through Four Points, because given any four points P0,P1,P2,P3 on the plane (with P0 at the origin), those points all lie on a single parabola of the form y = Gx^2 + Hx if we rotate the xy coordinate axes by an angle theta that satisfies the equation A tan(theta)^2 + B tan(theta) + C = 0 where A = b(y2^2 - y2 y3) - c(y1^2 - y1 y3) B = b(2 x2 y2 - x2 y3 - y2 x3) - c(2 x1 y1 - x1 y3 - y1 x3) C = b(x2^2 - x2 x3) - c(x1^2 - x1 x3) This quadratic has real roots iff B^2 - 4AC is greater than or equal to zero, and it's clear that a real parabola can pass through four points iff none of the points lies inside the triangle formed by the other three. Hence, we know that one of the points IS inside the triangle formed by the other three if and only if B^2 - 4AC = 4abc(a-b+c) < 0 The property of no point being inside the polygonal envelope of the other points in a set is called convexity, so the quantity abc(a-b+c) is an indicator of the convexity of a given set of four points. It's also worth noting that the four factors a,b,c,(a-b+c) are really twice the signed areas of the triangles on the four subsets of 3 points. Refer to the note Net Area, and Green's Theorem, which includes a derivation of the fact that the "net area" enclosed by a general n-sided polygon with vertices x[1],y[1] through x[n],y[n] (in order around the perimeter) is given by 1 n / \ A = - SUM ( x[i+1] y[i] - x[i] y[i+1] ) 2 i=1 \ / with the understanding that x[n+1] = x[1] and y[n+1] = y[1]. This is called the "signed area" because the result is positive or negative depending one whether the path is clockwise or counter-clockwise. So, twice the signed area enclosed by the path from P1 to P2 to P3 is A[P1,P2,P3] = (x1 y2 - x2 y1) + (x2 y3 - x3 y2) + (x3 y1 - x1 y3) Of course, if P0 is located at the xy origin, then twice the signed areas of the triangles enclosed by the paths P0,P1,P2, and P0,P1,P3, and P0,P2,P2 are simply A[P0,P1,P2] = x1 y2 - x2 y1 = a A[P0,P1,P3] = x1 y3 - x3 y1 = b A[P0,P2,P3] = x2 y3 - x3 y2 = c Substituting these into the preceding formula, we see that twice the fourth triangle's signed area can be expressed as A[P1,P2,P3] = a - b + c It's easy to see that four points are convex iff the product of the signed areas of the triangles on those four points (taken in any order) is positive, because of the invariance of the product under index permutations, and by inspection of the two possible topologies. Hence we arrive at the previous result, that four points (with P0 at the origin) are convex if and only if abc(a-b+c) is positive. Dispensing with the requirement for one of the points to be at the origin, it remains true that the product of the signed areas of the four triangles on four given points is positive iff those four points are convex. For convenience, let (ijk) denote twice the signed area enclosed by the piecewise-linear path from Pi to Pj to Pk to Pi. Then the four non-colinear points P1,P1,P2,P4 are convex if and only if (123)(124)(134)(234) > 0 It's important to note that while this total expression is invariant under permutations of the indices, it is not invariant under permutations of the indices in any individual factor. Each factor has an invariant magitude under permutations, but the sign can be reversed. Of the six possible permutations of the three indices in (ijk), three of them are positive three are negative, accordingly as the permutation is odd or even. Thus the invariance of the sign of the convexity indicator depends on maintaining a consistent order of the vertices in all four factors. Now, let us define the four-index symbol (ijkm) as the product of the four three-index symbols that can be formed from its indices, as follows (ijkm) = (ijk)(ijm)(ikm)(jkm) This is the convexity indicator for the four points Pi,Pj,Pk,Pm. Graham Herrick has pointed out that the above can be used to give an ingenious proof of the fact that any set of FIVE non-colinear points in the plane must contain at least one subset of four points that are arranged in a convex pattern. To prove this, he notes that if five points P1,..,P5 contained no convex subset of four points, then each of the five subsets consisting of four points must have a negative convexity indicator. Since the product of five negative numbers is negative, this implies (1234)(1235)(1245)(1345)(2345) < 0 However, if we express each of these four-index symbols in terms of their three-index factors we see that each distinct set of three indices appears in precisely two factors, so the above quantity can be expressed as / \ 2 ( (123)(124)(125)(134)(135)(145)(234)(235)(245)(345) ) \ / Being a square, this is necessarily positive. Hence, not all five of the four-point subsets can be non-convex. An odd number of them must be convex. Herrick notes that this is a special case of a conjecture of Erdos, which states that 2^(n-2)+1 non-colinear points in the plane always contain a convex n-gon. (This is known to be true for n=4 and n=5, but it remains conjectural for higher n.) For example, with n=4 the proposition asserts that any 5 non-colinear points in the plane contain a subset of 4 points arranged in a convex pattern. Likewise, with n=5 the proposition is that any 9 non-colinear points contains a subset of 5 points arranged in a convex pattern. The above proof that every 5-plex contains a convex 4-plex is interesting for several reasons. Notice that it doesn't rely on the specific form of the 4-index indicator, but simply on the fact that it factors symmetrically, such that the product of the indicators of every 4-plex in a given 5-plex is a square. We're prefectly entitled to define the 5-index indicator (ijkmn) as +1 if those 5 points are convex, and -1 if they are not, even though we may not know how to express it algebraically. It exists as a well-defined function, simply by virtue of the fact that every 5-plex is definitely either convex or not. Then we can form the product of all C(9,5)=126 5-index indicators based on 9 arbitrary (noncolinear) points, and see if this product has a special form (such as being a square) that we can exploit. Unfortunately, for all n greater than 4, the value of C(2^(n-2)+1,n) is even, so we are apparently blocked from applying Herrick's scheme to any more cases of Erdos' conjecture. Still, this raises some interesting questions, such as whether (ijkmn) can be expressed as a product of some function of the four- index subsets, i.e., whether the indicator (ijkmn) can be expressed as a symmetrical product of four-index functions (ijkmn) = F(ijkm) F(ijkn) F(ijmn) F(ikmn) F(jkmn) We know that F() is NOT the 4-index indicator, because these five points are convex iff all five of the 4-point indicators are positive, whereas the above product would give a positive indication iff an even number of the F() factors are negative. Nevertheless, this doesn't prove that no function F() exists. It simply means that F() isn't the 4-point indicator. Incidentally, notice that if we set F() to the 4-point indicator the resulting product is not invariant even up to sign, but has 24 distinct value in general (12 up to sign). The group of permutations S_5 splits into the cyclic and reversal actions. Any rotation of the indices leaves the product invariant, and reversing the indices changes the sign. Thus there are 12 independent values. What interests me most about the above proof is its implications for information "factoring". We've seen that, given four non-colinear points on the plane, we could transmit to each of four isolated people the coordinates of a unique set of three of those four points, along with a specific ordering of those points (up to even permutations), and those people could independently compute the three-point indicator for their respective sets of points (normalized to +1 or -1), such that the product of all their numbers indicates whether or not the total set of four points is convex. This is true in spite of the fact that none of the four people has enough information to assess the convexity of the four-point set. Moreover, we can arrange for the returned values to be either positive or negative (by permuting the order) with equal frequency on a sequence of trials. In other words, we're free to reverse the signs of the factors (in unison) without affecting the overall result. This is intriguingly similar to situations involving quantum mechanical phenomena, such as EPR-type experiments, in which the information available at separate locations is unable to convey any knowledge of the combined result, and yet the individual results seem to exhibit, upon combination, some correlative aspects. In other words, each of two observers may see +1 and -1 (represent- ing, say, spin UP or spin DOWN) an equal percentage of the time, apparently randomly distributed, but when they get together and compare corresponding observations they find correlations, such that their product is not randomly distributed, and moreover the factors are correlated in a non-linear way which defies ordinary causal explanation based on the idea that each indicator has a definite value prior to observation. In the case of convexity indicators, this can be attributed to the fact that the three given points specified to an individual observer can yield +1 or -1, depending on the presumed ordering of those points. This amount to determining a "basis" for evaluating those points, and when the observers come together they must reconcile their bases and establish a consistent ordering, when then ensures that the product of the indicators (interpreted on this common basis) is the four-point indicator.

Return to MathPages Main Menu