Browse · MathNet
PrintIrska
Ireland geometry
Problem
Let be a set of different points in the plane so that no three lie on a line. Show that there are at least triangles whose vertices are among the points of and such that the triangles do not contain any other points of .
Solution
Choose two points and from , and consider the half plane with boundary the line , and containing at least one other point of . Now select a point of in the interior of whose distance from the line is a minimum. If there are several such points, choose an arbitrary one.
Now claim that the triangle does not contain any other point of , apart from , , and . Suppose there is a point which is in the interior of the triangle . Then and so the altitude from of the triangle is less than the altitude from of the triangle . This contradicts the choice of .
Suppose that there are pairs of points in with the property that the whole of the set lies in one of the two half planes with boundary the line . Such pairs are adjacent vertices of the convex hull of and so . For each of these pairs we have shown that there is at least one triangle , which is “empty”, that is it does not contain any of the remaining points of .
The remaining pairs have the property that there are at least two “empty” triangles . Now sum all these triangles over all the pairs and we get in all such triangles. Each is counted at most three times so the number of “empty” triangles is at least .
Now claim that the triangle does not contain any other point of , apart from , , and . Suppose there is a point which is in the interior of the triangle . Then and so the altitude from of the triangle is less than the altitude from of the triangle . This contradicts the choice of .
Suppose that there are pairs of points in with the property that the whole of the set lies in one of the two half planes with boundary the line . Such pairs are adjacent vertices of the convex hull of and so . For each of these pairs we have shown that there is at least one triangle , which is “empty”, that is it does not contain any of the remaining points of .
The remaining pairs have the property that there are at least two “empty” triangles . Now sum all these triangles over all the pairs and we get in all such triangles. Each is counted at most three times so the number of “empty” triangles is at least .
Techniques
Convex hullsCounting two waysColoring schemes, extremal argumentsDistance chasing