Geometry and the extremal principle
Inner products for distances and angles, Gram determinants, areas via determinants and the shoelace formula, convex sets, Helly and separation, Pick, and the extremal principle with compactness.
What to know by heart
Inner product. For :
The angle is obtuse exactly when , and right exactly when the product is . So a condition on distances becomes a condition on the signs of inner products.
Determinants, areas, volumes. The signed area of the triangle with vertices is
positive when the vertices are in counterclockwise order and zero exactly when they are collinear. The -dimensional simplex with vertices has volume .
Shoelace formula. For a simple polygon with and indices modulo :
Gram determinant. For the matrix is positive semidefinite, , and is the square of the -dimensional volume of the parallelepiped spanned by the .
Convex sets. The convex hull is the set of convex combinations with , , . In , points suffice (Carathéodory); in the plane, every point of the hull lies in a triangle with vertices from .
Helly in the plane. If () are convex and every three of them have a common point, then all of them have a common point. For an infinite family the sets must moreover be compact.
Separation. Two disjoint, nonempty, compact convex subsets of are strictly separated by a hyperplane.
Pick. For a simple polygon with vertices in , with interior and boundary lattice points:
The segment from to contains lattice points (endpoints included).
Isoperimetric inequality. A closed curve of length enclosing area satisfies , with equality only for the circle. Among -gons with given perimeter, the regular one has the largest area.
Extremal principle. On a finite (or compact) set every real quantity (continuous, in the compact case) has a maximum and a minimum. Choose the object that makes a well-chosen quantity extremal, assume the claim fails, and build an even more extreme object: contradiction.
The standard lemmas
Lemma 1 (four points). For all :
with equality exactly when , that is when is a (possibly degenerate) parallelogram.
Proof. Expand every as above. The left-hand side becomes , and the expansion of gives exactly the same.
Lemma 2 (Gram). Let be the matrix with columns , so .
- , so is positive semidefinite, and exactly when . Hence exactly when the are linearly dependent.
- If they are independent, Gram–Schmidt gives , where has orthonormal columns () and is upper triangular with the distance of from . Then and . The repeated product "base times height" is exactly the volume of the parallelepiped.
For : the triangle in has area with , . Conversely, every positive semidefinite with is the Gram matrix of vectors in : from the spectral decomposition we get with , and has at most nonzero rows.
Lemma 3 (shoelace formula). By Green's theorem, the area of a region with positively oriented boundary is . On the side from to , with and , the integral is . Summing, the terms telescope cyclically to and what remains is . The absolute value covers the clockwise order.
Reading with triangles: by the determinant formula with , each term is the signed area of the triangle . So the formula adds up the triangles from the origin to each side; those traversed clockwise count negatively and remove exactly what lies outside the polygon.
Consequence: every polygon with vertices in has area in .
Lemma 4 (Radon and Helly in the plane). Radon: four points can be split into two groups with intersecting convex hulls.
Proof. The three vectors of are dependent, so there are , not all zero, with and . Let , the rest, and . The point
lies in both hulls.
Helly for . Take and split by Radon into , with a common point . For each : if , all with lie in , so ; if , then and in the same way . For : replace by . By the case , every three of the new sets intersect, and induction applies.
Lemma 5 (separation via the closest pair). Let be disjoint, nonempty, compact convex sets. The map is continuous on the compact set , so it attains a minimum at some , with . Put . If for some , then for :
for small , a contradiction. So on and, symmetrically, on . Since , the hyperplane separates strictly.
Lemma 6 (Pick, sketch). The quantity is additive when two lattice polygons are glued along a common side (the points of the common side become interior, and the corrects the two endpoints). The formula holds for rectangles with sides on the axes (counting), hence for their right triangles, hence for every triangle (subtracting right triangles from a rectangle), hence for every simple polygon (triangulation). Consequence: a lattice triangle with no other lattice points has area .
Lemma 7 (the farthest pair). If are two points of a finite at maximal distance, then all of lies between the two hyperplanes through and perpendicular to . Indeed, if , then
In particular are vertices of .
Lemma 8 (Sylvester–Gallai). If a finite does not lie on a single line, some line contains exactly two points of .
Proof. Among the pairs with a line through at least two points of and (finitely many, and at least one), choose the one with the smallest distance , where is the projection of onto . If had three points of , two of them, and , would lie on the same closed half-line of starting at , with . The point is on the segment , so its distance from the line is at most that of , namely (hypotenuse). The pair is admissible and has a smaller distance: contradiction.
Lemma 9 (a maximal packing is a net). Let be bounded and . A set of points of with pairwise distances has bounded size: the balls of radius around them are disjoint and lie in a bounded set. Take such a set of maximal size. Then every point of is at distance less than from some point of the set, otherwise we could add it.
Typical tricks
- Choose the origin. At the centroid (), at a vertex or at a given interior point. Then every condition on distances or angles becomes a condition on the .
- Pass to a Gram matrix. When the pairwise distances are known, the inner products of the are completely determined. Positive semidefiniteness and bound the number of points.
- Determinant for collinearity and orientation. The sign of tells on which side of the point lies; it changes sign only when crosses the line.
- A linear functional. For finite and generic , the point maximizing is a vertex of . It is the quickest extremal principle.
- Sections. Area or volume as the integral of the lengths or areas of the sections (Cavalieri). If every section is at least something, integrate the bound.
- Parities on the lattice. Among five points of , two have the same pair , so their midpoint is a lattice point.
- Averaging over a symmetric configuration. If a quantity has sum over two symmetric points, one of the two gives .
- Existence first. Before taking "the largest triangle" or "the closest pair", show it exists: a finite set, or a continuous function on a compact set (Weierstrass). In an open disk there is no inscribed triangle of maximal area, since the supremum is not attained.
- Compactness for limits of configurations. A sequence of -tuples of points of a compact set has a convergent subsequence (Bolzano–Weierstrass), so a minimizing sequence gives a minimizer when the quantity is continuous. Also: if every finite subfamily of a family of compact sets intersects, the whole family intersects, which is why Helly extends to infinite families of compact convex sets.
- Pitfalls. Helly needs convexity and "every three", not "every two". Pick needs a simple polygon without holes and with lattice vertices. The signed area is not the area when the polygon self-intersects.
How they appear in the IMC
- IMC 2001, day 2, problem 3: points on a sphere with large pairwise distances. The condition on distances becomes a condition on the sign of inner products.
- IMC 2008, day 2, problem 6: equidistant points in a Hilbert space. Inner products and the choice of a suitable centre.
- IMC 2015, day 1, problem 5: a point inside a simplex and obtuse angles. The point is written as a convex combination of the vertices and the angles become signs of inner products.
- IMC 2004, day 2, problem 3: sums of distances in the unit disk. Existence of a point by choosing extremal or symmetric positions.
- IMC 2009, day 2, problem 1: the volume of a set defined by a distance inequality. Coordinates and sections.
- IMC 2024, day 1, problem 5: the convex hull of random points. " is not in the hull" is described by a hyperplane through that leaves all points on one side.
- IMC 2023, day 2, problem 9: convex subsets of the cube with disjoint projections. Convexity and volumes.
- IMC 2026, day 2, problem 7: the area of a union of line segments. Horizontal sections for the lower bound and an extremal configuration that attains it.
- IMC 2025, day 2, problem 7: sets of integers closed under doubling and averaging. Not geometry, but the solution rests on the extremal principle: the smallest element, and the largest element below a given one.
Contest problems using these tools
No problems with these tools yet.