Chapter 35: Geometric Combinatorics

How can intersecting every small subfamily force a common point?

Suppose several geometric constraints each describe a region of allowed positions. Testing every pair is tempting: if any two requirements can be met together, perhaps all can. That conclusion is true for intervals on a line, but false for arbitrary convex regions in the plane. The missing ingredient is dimension.

A set $C\subseteq\mathbb R^d$ is convex if $(1-t)x+ty\in C$ whenever $x,y\in C$ and $0\le t\le1$. Thus the whole segment between any two members remains in the set. Intersections of convex sets are convex. A convex combination is $\sum_i\lambda_i p_i$ with $\lambda_i\ge0$ and $\sum_i\lambda_i=1$; the convex hull of a point set consists of its finite convex combinations. Disks, halfspaces, and rectangular boxes are convex; a union of separated disks generally is not.

Helly's theorem, finite form. For a finite family of at least $d+1$ convex subsets of $\mathbb R^d$, if every $d+1$ members have a common point, then the entire family has a common point. Equivalently, if the total intersection is empty, some subfamily of at most $d+1$ already has empty intersection. In the plane the correct local test uses triples. Convexity and finiteness are essential hypotheses in this statement.

Here is the proof foundation needed for the concluding investigation. Any $d+2$ points have an affine dependence: their lifted vectors $(p_i,1)\in\mathbb R^{d+1}$ satisfy $\sum_i a_i(p_i,1)=0$ for some coefficients not all zero. Hence $\sum_i a_i=0$ and $\sum_i a_i p_i=0$. Positive and negative coefficients both occur. Dividing by their common total magnitude yields one point expressed as a convex combination of the positive-coefficient points and also of the negative-coefficient points. Assign zero-coefficient points to either side. This is Radon's partition lemma: two disjoint nonempty groups have intersecting convex hulls.

To deduce Helly, suppose a finite family has empty intersection, and choose an inclusion-minimal empty subfamily $C_1,\ldots,C_r$. If $r\le d+1$, the desired certificate is already found. Otherwise, for each $i$, choose a witness $p_i$ in every $C_j$ except $C_i$. Apply Radon's lemma to $p_1,\ldots,p_{d+2}$ and let $q$ belong to both resulting convex hulls. For any $j\le d+2$, the group not containing index $j$ lies entirely in $C_j$, so convexity puts $q$ in $C_j$. For any remaining $j$, all selected points lie in $C_j$. Thus $q$ belongs to every member of the minimal family, a contradiction. This proves the finite theorem.

The other foundation is incidence counting. For a finite set of points $P$ and a finite set of distinct lines $L$ in the real plane, an incidence is a pair $(p,\ell)$ with $p\in\ell$. Write $I(P,L)$ for their number. It can be counted by summing points per line or lines per point. Exact equations such as $y=ax+b$ give reproducible constructions without relying on a picture. These definitions, the convexity proof above, and elementary coordinate algebra suffice for the final investigation; Sections 35.1–35.10 are optional extensions. Linear algebra explains affine dependence, but no advanced computational geometry background is required.

35.1 Convexity and Helly's theorem

Optional extension; not required to complete the chapter foundation.

A halfspace is a set $\{x:a\cdot x\le b\}$ for a nonzero vector $a$ and scalar $b$. Its convexity follows by taking the same convex combination of two valid inequalities. A finite intersection of halfspaces is a convex polyhedron. Helly applies to these feasible regions without requiring boundedness, compactness, or full dimension.

The theorem's intuition is that infeasibility cannot require an arbitrarily large irreducible list of convex constraints in a fixed dimension. The witness-and-Radon argument in the introduction proves this: too many individually essential constraints produce points whose affine dependence forces a common feasible point. Its contrapositive is often the useful formulation: empty intersection has a certificate of size at most $d+1$.

Solved example. Let $C_1=\{x\ge0\}$, $C_2=\{y\ge0\}$, $C_3=\{x+y\le2\}$, and $C_4=\{x+y\ge1\}$ in the plane. The full intersection is the closed region in the first quadrant between the two diagonal lines. The point $(1,0)$ belongs to all four, and therefore witnesses every triple intersection as well. In this example the region's vertices are $(1,0),(2,0),(0,2),(0,1)$. Convexity of the intersection is immediate, while vertex enumeration provides an additional finite description.

There is a useful subtlety when the family has fewer than $d+1$ members: the phrase “every $d+1$ intersect” would be vacuous. For families of arbitrary size, formulate the assumption as every subfamily of at most $d+1$ intersects. For a family with at least $d+1$ members, the two formulations agree because a smaller subfamily can be extended to one of size $d+1$.

Finiteness cannot simply be dropped. The intervals $[n,\infty)$, for positive integers $n$, are convex and every finite subfamily intersects, but their infinite intersection is empty. An infinite-family extension needs an additional condition, such as closed sets with one compact member; compactness then upgrades finite intersection information to a global point.

Exercise. Let $D_1=\{x\ge0\}$, $D_2=\{y\ge0\}$, $D_3=\{x+y\le-1\}$, and $D_4=\{x\le10\}$. Give an infeasibility certificate of size at most three. Hint: the last constraint is irrelevant to the contradiction. Solution: $D_1,D_2,D_3$ already have empty intersection, since the first two imply $x+y\ge0$. Each of their pairs intersects at a point listed in the motivating card, so this three-member certificate is inclusion-minimal.

35.2 Carathéodory's and Radon's theorems

Optional extension; not required to complete the chapter foundation.

Carathéodory's theorem. If $q\in\operatorname{conv}(S)$ for $S\subseteq\mathbb R^d$, then $q$ lies in the convex hull of at most $d+1$ points of $S$. The conclusion concerns a representation of one point; it does not say every convex hull has at most $d+1$ vertices.

To prove it, start with a finite convex combination for $q$, discard zero weights, and suppose more than $d+1$ positive weights remain. An affine dependence gives coefficients $a_i$ with $\sum_i a_i=0$ and $\sum_i a_i p_i=0$. Both signs occur. Let

$$ t=\min_{a_i\gt0}\frac{\lambda_i}{a_i},\qquad \lambda_i'=\lambda_i-ta_i. $$

The new weights are nonnegative, still sum to one, and represent the same $q$. At least one becomes zero. Iterating removes excess support and proves the theorem. This argument is an exact support-reduction procedure.

Radon's theorem. Any $d+2$ points in $\mathbb R^d$ can be partitioned into two nonempty groups whose convex hulls meet. Points need not be in general position. The lifted-vector proof in the introduction establishes the result; separating the signs of the dependence produces the partition explicitly. Carathéodory reduces support within one representation; Radon produces two representations of the same point from disjoint groups.

Exercise. Find a Radon partition for $(0,0),(3,0),(0,3),(1,1)$. Hint: one point is an average of the other three. Solution: $(1,1)$ is one third of the sum of the first three points. Use the singleton group $\{(1,1)\}$ and the group of the three triangle vertices. Their convex hulls meet at $(1,1)$. The partition has unequal group sizes, which the theorem allows.

35.3 Hyperplane arrangements

Optional extension; not required to complete the chapter foundation.

An affine hyperplane in $\mathbb R^d$ is $\{x:a\cdot x=b\}$ with $a\ne0$. An arrangement is a finite collection of distinct hyperplanes, together with the subdivision they induce. Full-dimensional regions are connected components of their complement. A region is described by strict signs of the defining affine functions; it is convex because it is an intersection of open halfspaces. Thus a realizable sign pattern determines one region, rather than several disconnected pieces.

For $n$ hyperplanes in general position, the maximum number of regions is

$$ R_d(n)=\sum_{j=0}^d\binom nj. $$

Here general position means that any $j\le d$ hyperplanes meet in codimension $j$, and no $d+1$ share a point. Adding one hyperplane splits exactly the old regions that meet it. The traces of the preceding hyperplanes on the new one form a general-position arrangement in dimension $d-1$, giving $R_d(n)=R_d(n-1)+R_{d-1}(n-1)$. With $R_d(0)=1$ and $R_0(n)=1$, Pascal's identity proves the formula. Without general position it remains an upper bound.

Solved example. Take $\ell_1:x=0$, $\ell_2:y=0$, and $\ell_3:x+y=1$. Their pairwise intersections are $(0,0),(0,1),(1,0)$, all distinct. There are seven regions, one of which is bounded: the open triangle $x\gt0,y\gt0,x+y\lt1$. The diagram labels all seven by representatives; signs are taken in the order $(x,y,x+y-1)$. The pattern $(-,-,+)$ is impossible since negative $x,y$ force $x+y-1\lt0$. All other seven patterns appear.

The finite window clips the three infinite lines for display. Only the three colored lines belong to the arrangement; the frame is not an additional constraint. Each dot is a region representative, not another intersection vertex.

Exercise. How many regions do three distinct concurrent lines create? Why is the general-position formula not attained? Hint: add the third line through the existing intersection. Solution: the first line gives two regions, the second gives four, and the third splits only two more, giving six. Three lines share one point, violating general position. If all three were parallel, they would create only four regions.

35.4 Incidence geometry and Szemerédi–Trotter theorem

Optional extension; not required to complete the chapter foundation.

Let $P$ be $n$ distinct points and $L$ be $m$ distinct straight lines in $\mathbb R^2$. The incidence bipartite graph has parts $P,L$ and an edge for each containment. Two distinct points determine at most one line, so the graph contains no $K_{2,2}$. This exclusion alone gives an extremal-graph bound, but the planar drawing of the lines permits a stronger estimate.

Szemerédi–Trotter theorem. There is an absolute constant $C$ such that

$$ I(P,L)\le C\bigl(n^{2/3}m^{2/3}+n+m\bigr). $$

The hypotheses concern distinct points and distinct real straight lines; duplicates counted with multiplicity need a different formulation. The additive terms cannot be discarded, for instance when one line contains every point. See the original Szemerédi–Trotter paper, Extremal problems in discrete geometry (1983).

Proof using the crossing lemma. Join consecutive incident points along each line containing at least two points. The resulting graph is simple: two vertices cannot be joined along two distinct lines. If $e$ is its edge count, then $e\ge I-m$. The interior of an edge contains no point of $P$. Different supporting lines cross at most once, so this drawing has at most $\binom m2$ crossing edge pairs. If several crossings coincide, a small local perturbation separates them without exceeding the pair count.

The crossing lemma says that a simple graph with $n$ vertices and $e\ge4n$ edges has crossing number at least $c e^3/n^2$ for an absolute $c\gt0$. Under this condition, comparing upper and lower bounds gives $e=O(n^{2/3}m^{2/3})$. Otherwise $e\lt4n$. In both cases $I\le e+m$ gives the theorem. This derivation uses the crossing lemma as an external graph-theoretic ingredient; its random-sampling proof is not reproduced here.

Solved example. Let $P=\{1,2,3\}^2$, and take the three horizontal and three vertical lines through this grid. There are nine points, six lines, and eighteen incidences. Each line contains three points and each point lies on two lines. The construction has no crossing away from $P$: the consecutive-point graph is planar. Its twelve edges satisfy $e=I-m=12$, placing it in the low-edge branch of the proof. Not every example realizes the theorem's leading term.

A useful consequence is a bound on $k$-rich lines, meaning lines with at least $k$ points of $P$, for $k\ge2$. Their number is $O(n^2/k^3+n/k)$. Apply the incidence bound to those lines and use $I\ge km$; for sufficiently large $k$, absorb the $Cm$ term and separate the remaining two terms. For bounded $k$, the fact that each such line contains a pair gives at most $\binom n2$ lines, consistent with the stated bound.

Exercise. Count incidences between the same nine grid points and the four lines $x=1,x=3,y=1,y=3$. Hint: corners count once for each incident line. Solution: each of four lines contains three points, so $I=12$. Equivalently, four corners contribute eight incidences, four noncorner boundary points contribute four, and the center contributes zero.

35.5 Point-line and point-circle incidences

Optional extension; not required to complete the chapter foundation.

For any point set $P$ and curve family $\mathcal C$, define $I(P,\mathcal C)=\sum_{C\in\mathcal C}|P\cap C|$. A circle here is an ordinary Euclidean circle of strictly positive radius, specified by $(x-a)^2+(y-b)^2=r^2$. Distinct circles can share two points, whereas distinct straight lines share at most one. Consequently, the straight-line crossing argument cannot be transferred unchanged.

A precise elementary bound follows from counting circle pairs. Let $s_p$ be the number of circles through $p$, and let $m=|\mathcal C|$, $n=|P|$. Since a pair of distinct circles meets in at most two points,

$$ \sum_{p\in P}\binom{s_p}{2}\le2\binom m2. $$

When $n\gt0$, Cauchy–Schwarz gives $I^2/n\le\sum_p s_p^2\le I+2m(m-1)$. Thus

$$ I\le\frac{n+\sqrt{n^2+8nm(m-1)}}2\le n+\sqrt{2n}\,m. $$

This is a proved elementary estimate, not a sharp general point-circle incidence theorem. Circle geometry has additional structure, and sharper results require other tools and precise hypotheses. A second elementary constraint is that three distinct points lie on at most one circle: if noncollinear they determine its center, and if collinear no circle passes through all three. Therefore $\sum_{C\in\mathcal C}\binom{|P\cap C|}{3}\le\binom n3$.

Solved example. Take the four unit-square vertices. Its four side lines each contain two points, for eight incidences; its two diagonal lines add four, giving twelve for the six-line family. The circle centered at $(1/2,1/2)$ with squared radius $1/2$ contains all four points, giving four point-circle incidences. Every three square vertices determine that same circle. The configurations illustrate why counting point triples, rather than pairs, is natural for arbitrary circles.

Exact coordinates make these tests algebraic: a point belongs to a line when its linear equation vanishes, and to a circle when its squared-distance equation holds. Use squared radii and squared distances to avoid unnecessary square roots. Approximate equality under a tolerance describes a different, noisy-data problem.

Exercise. Let $P=\{(-1,0),(1,0),(0,1),(0,-1)\}$ and let the circles have centers $(0,0)$ and $(0,1)$, both of radius one. Count incidences. Hint: evaluate the squared-distance equation at all four points. Solution: the first circle contains all four. The squared distances from $(0,1)$ are $2,2,0,4$, none equal to one. Hence the second contains none and $I=4$. A point at a circle's center is not on its circumference.

35.6 Erdős distinct-distances problem

Optional extension; not required to complete the chapter foundation.

For a finite set $P$ of $n$ distinct points in $\mathbb R^2$, define

$$ \Delta(P)=\{\|p-q\|:p,q\in P,\ p\ne q\},\qquad D(P)=|\Delta(P)|. $$

There are $\binom n2$ unordered pairs, but many pairs may yield the same distance. The extremal question asks how small $D(P)$ can be. If all points lie on a line at consecutive integer coordinates, they determine $n-1$ distances. A planar grid creates more repetitions, illustrating why the question is geometric rather than a count of pairs alone.

A major established result of Guth and Katz (2015) is that every such set, for $n\ge2$, satisfies $D(P)\ge c n/\log n$ for an absolute positive constant $c$. This is the classical bound being taught here, rather than a claim that the exact extremal growth or a best current estimate has been settled.

Proof sketch; omitted prerequisites. Group pairs by their distances and bound the number of equal-distance quadruples. The Elekes–Sharir framework translates rigid motions matching segments into an incidence problem for lines in three-dimensional parameter space. Guth and Katz control that problem using polynomial partitioning and the geometry of ruled surfaces. Planar Szemerédi–Trotter alone does not supply these three-dimensional estimates. Those algebraic-geometric ingredients are omitted.

Solved example. For $P=\{0,1,2\}^2$, work with squared distances. The complete multiplicity table for unordered pairs is

The counts sum to $36=\binom92$, and $D(P)=5$. For example, a horizontal unit step has six placements; the vertical ones contribute six more. For a displacement with both coordinates nonzero, counting both slope signs supplies the corresponding diagonal placements.

Let $M_s$ denote the unordered multiplicity at squared distance $s$. Cauchy–Schwarz gives

$$ \binom{n}{2}^{2}=\left(\sum_s M_s\right)^2\le D(P)\sum_s M_s^2. $$

Here the squared multiplicities sum to $312$, so $D(P)\ge1296/312=54/13$. Since $D(P)$ is an integer, this already gives $D(P)\ge5$, agreeing with the exact table. The inequality explains how controlling repeated distances yields a lower bound on distinct ones.

Exercise. Determine all squared distances for a rectangle with vertices $(0,0),(2,0),(2,1),(0,1)$. Hint: distinguish the two side lengths and the diagonals. Solution: the values are $1,4,5$, each occurring twice among the six unordered pairs. Thus $D=3$, unlike the square, whose two side lengths coincide and yield only two distinct distances.

35.7 Convex and lattice polytopes

Optional extension; not required to complete the chapter foundation.

A convex polytope is the convex hull of finitely many points. A vertex is an extreme point, meaning it is not a nontrivial convex combination of two other points of the polytope. A face is the set on which a linear functional attains its maximum; proper faces have dimension below that of the polytope. A full-dimensional polytope in $\mathbb R^d$ has facets of dimension $d-1$ and edges of dimension one.

These objects have both geometric and combinatorial descriptions. A three-dimensional convex polytope has a planar boundary graph and satisfies $v-e+f=2$, with vertices, edges, and facets counted. A cube has $(v,e,f)=(8,12,6)$, while a tetrahedron has $(4,6,4)$. These counts concern boundary faces, excluding the empty face and the whole solid. The Euler relation follows from the planar graph formula after projecting one facet to the outside face.

A lattice polytope has vertices in $\mathbb Z^d$. Its Ehrhart function is $L_Q(t)=|tQ\cap\mathbb Z^d|$ for nonnegative integers $t$. Ehrhart's theorem states this function is a polynomial of degree equal to the polytope's dimension, with leading coefficient its volume measured in the affine lattice. In the full-dimensional planar case this is ordinary Euclidean area. Rational vertices instead lead generally to a quasipolynomial, so integrality of vertices matters.

Solved example. Let $Q=\operatorname{conv}\{(0,0),(2,0),(0,2)\}$. Its area is two. The lattice points of $tQ$ satisfy $x,y\ge0$ and $x+y\le2t$. For each $x=0,\ldots,2t$, there are $2t-x+1$ choices of $y$. Hence

$$ L_Q(t)=\sum_{x=0}^{2t}(2t-x+1)=\frac{(2t+1)(2t+2)}2=2t^2+3t+1. $$

At $t=1$ there are six points: $(0,0),(1,0),(2,0),(0,1),(1,1),(0,2)$. All are boundary points. Pick's theorem for a simple lattice polygon states $\operatorname{area}=I+B/2-1$, where $I,B$ count interior and boundary lattice points; here $I=0,B=6$, giving area two. This verifies the example independently. Pick's theorem and the general Ehrhart theorem are stated results; their general proofs are outside this section.

Exercise. Count lattice points in the dilation of the unit square, and recover its area from the leading coefficient. Hint: both coordinates range independently from zero to $t$. Solution: $L(t)=(t+1)^2=t^2+2t+1$, whose leading coefficient is one, the square's area. At $t=0$ the dilation is one point, explaining the constant term.

35.8 Discrete and computational geometry connections

Optional extension; not required to complete the chapter foundation.

Discrete geometry bounds the possible configurations; computational geometry uses those bounds to organize algorithms. An arrangement of $n$ planar lines can have $\binom n2$ vertices and $1+n+\binom n2$ regions, so an algorithm explicitly reporting all intersections cannot have a subquadratic worst-case output time. This is an output-size obstruction, independent of which data structure is used.

For convex hulls, the elementary orientation predicate is

$$ \operatorname{orient}(a,b,c)=(b_x-a_x)(c_y-a_y)-(b_y-a_y)(c_x-a_x). $$

Its sign distinguishes left turns, right turns, and collinearity. A monotone-chain hull algorithm sorts the points lexicographically, builds lower and upper chains, and removes the last chain point whenever a new point creates a non-left turn. Each point is pushed once and popped at most once on each chain, giving linear work after sorting and total $O(n\log n)$ time in a comparison model with constant-cost exact predicates. Bit complexity requires accounting for coordinate sizes.

Solved example. Take $P=\{(0,0),(1,1),(0,2),(2,0),(2,2)\}$. Its sorted order is $(0,0),(0,2),(1,1),(2,0),(2,2)$. In the lower chain, inserting $(1,1)$ makes orientation $-2$ with the first two points, so $(0,2)$ is removed. Inserting $(2,0)$ then makes orientation $-2$ with $(0,0),(1,1)$, so the interior point is removed. The completed lower chain is $(0,0),(2,0),(2,2)$. The reverse pass gives $(2,2),(0,2),(0,0)$. Combining them yields the four square corners.

Correctness rests on the invariant that the chain supports all points processed so far on its permitted side. A right turn makes the middle vertex incompatible with the lower convex boundary; removing it restores the invariant. The upper pass supplies the complementary supporting chain. The collinear rule determines whether redundant boundary points are retained; the rule above removes them and returns only extreme vertices.

For full algorithm engineering, including robust predicates and geometric degeneracies, continue with the dedicated MIT computational geometry course. Here the focus is the combinatorial output and invariant. Integer determinants can be exact, while arbitrary floating-point coordinates require a deliberate predicate strategy; a rounded sign can change the hull's combinatorial structure.

Exercise. Apply the collinear rule to $(0,0),(1,0),(2,0),(1,1)$. Hint: the first three have determinant zero. Solution: $(1,0)$ is removed from the lower boundary. The hull vertices are $(0,0),(2,0),(1,1)$. The omitted point remains on the hull boundary but is not an extreme vertex. Returning all boundary points would require a different collinearity policy.

35.9 Geometric transversal theory

Optional extension; not required to complete the chapter foundation.

A transversal meets every member of a family of sets. A point transversal is a common point; a line transversal is one line intersecting every set. A finite point set hitting every member is a piercing set, and its minimum size is the piercing number $\tau$. The maximum number of pairwise disjoint members is the packing number $\nu$. Always $\tau\ge\nu$, because one point cannot hit two disjoint members.

For a finite family of closed bounded intervals on a line, equality holds: $\tau=\nu$. Choose an interval with the smallest right endpoint $r$, place a piercing point at $r$, remove every interval containing it, and repeat. Every remaining interval starts strictly to the right of $r$: its right endpoint is at least $r$, and it does not contain $r$. The intervals selected in successive rounds are therefore pairwise disjoint. If the algorithm uses $k$ points, these selected intervals certify $\nu\ge k$, while the constructed piercing set proves $\tau\le k$. Together with $\tau\ge\nu$, this proves optimality.

Solved example. For $[0,2],[1,3],[5/2,4],[7/2,5]$, the algorithm first chooses $2$, removing the first two intervals, then $4$, removing the last two. Thus $\tau=2$. The disjoint intervals $[0,2]$ and $[5/2,4]$ certify that one point cannot suffice. This is a primal solution and a matching combinatorial lower bound.

A line transversal is different from a common point. Consider the rectangles $[0,2]\times[0,1]$, $[1,3]\times[3,4]$, and $[3/2,5/2]\times[6,7]$. Their intersection is empty because their vertical ranges are disjoint. Yet the vertical line $x=7/4$ meets all three. A vertical line $x=t$ meets a rectangle exactly when $t$ lies in its horizontal projection. Those projections have common intersection $[3/2,2]$.

Thus fixed-direction line transversals for convex compact sets reduce to intersection of intervals on the perpendicular axis, where pairwise projection overlap suffices. Allowing the line direction to vary changes the parameter space; one cannot apply planar Helly to arbitrary line parameters without establishing convexity of the feasible parameter sets.

Exercise. Find the complete set of vertical line transversals for the three rectangles above. Hint: intersect their horizontal projections. Solution: the permitted parameters are $[0,2]\cap[1,3]\cap[3/2,5/2]=[3/2,2]$. Each such vertical line meets all three, including at boundary points when an endpoint parameter is used.

35.10 Discrete geometric optimization

Optional extension; not required to complete the chapter foundation.

A fundamental facility-location problem chooses a center $c\in\mathbb R^2$ minimizing $R(c)=\max_{p\in P}\|p-c\|$ for a finite nonempty demand set $P$. This is the minimum enclosing disk problem. A minimizer exists because $R$ is continuous and tends to infinity as $\|c\|$ does; restricting to a sufficiently large compact disk preserves the minimum.

At a proposed radius $r$, each demand point permits centers in the closed disk $D(p,r)$. Feasibility is exactly $\bigcap_{p\in P}D(p,r)\ne\varnothing$. These are convex sets, so Helly implies that infeasibility has a certificate involving at most three demands. This decision consequence does not say that three arbitrary points determine the optimal disk.

There is also an optimization support theorem: an optimal disk is certified by at most three boundary demands. To see why, its center must lie in the convex hull of its boundary demands. Otherwise a separating direction moves the center slightly toward every boundary demand, strictly reducing their distances; the finitely many nonboundary demands retain their strict margin. That contradicts optimality. More explicitly, projecting the center onto the convex hull provides a direction with positive dot product toward every boundary point.

Carathéodory now supplies at most three boundary points $p_i$ and nonnegative weights $\lambda_i$ with $c=\sum_i\lambda_i p_i$ and $\sum_i\lambda_i=1$. For any proposed center $z$, expansion gives

$$ \sum_i\lambda_i\|p_i-z\|^2=R(c)^2+\|z-c\|^2. $$

Some supported point is therefore at distance at least $R(c)$ from $z$. These few demands certify the global optimum. The identity also proves uniqueness of the optimal center: a different center would require a strictly larger radius to cover the supported points.

Solved example. Let $P=\{(0,0),(4,0),(2,3)\}$. The center $c=(2,5/6)$ has squared distance $169/36$ from each demand, so its radius is $13/6$. It is the convex combination with weights $13/36,13/36,5/18$: the horizontal coordinate is two, and the vertical coordinate is $5/6$. All weights are positive and sum to one. The weighted identity proves that every center has maximum squared distance at least $169/36$, with equality only at $c$.

Pairwise feasibility can miss this optimum. At radius two, each pair of demand disks intersects because every pair of demand points is separated by at most four. The disks around $(0,0)$ and $(4,0)$ meet only at $(2,0)$, which lies at distance three from $(2,3)$. Their triple intersection is empty. The exact optimal radius is larger than the largest pairwise half-distance.

A combinatorial candidate method enumerates disks supported by one, two, or three points: radius-zero disks, pair-diameter disks, and circumdisks of noncollinear triples. Test each candidate against every demand, and take the smallest covering disk. The support theorem proves completeness; enumerating $O(n^3)$ candidates and using $O(n)$ containment tests each gives $O(n^4)$ arithmetic operations. This is a transparent correctness method, not an efficient production implementation. The dedicated computational geometry course supplies the broader context for robust predicates and faster geometric algorithms.

Exercise. Find the minimum enclosing disk of $(0,0),(4,0),(0,3)$. Hint: the longest side has length five. Solution: the diameter disk of $(4,0),(0,3)$ has center $(2,3/2)$ and radius $5/2$. The remaining point is also at distance $5/2$. Any covering disk has radius at least half the longest pair distance, so this disk is optimal. Three boundary contacts do not necessarily require three support points; the longest-side pair already certifies it.

Prove a convexity consequence and investigate an incidence construction

This investigation combines local feasibility certificates with a configuration achieving the leading scale in the point-line incidence theorem. All necessary definitions and the finite Helly proof appear in the introduction. Exact rational calculations provide the proofs; a drawing or numerical experiment is useful for exploration and checking, but must not replace the stated reasoning.

Worked solution: disks and the convexity consequence. If $x,y\in D(p,r)$ and $0\le t\le1$, then

$$ \|(1-t)x+ty-p\|\le(1-t)\|x-p\|+t\|y-p\|\le r. $$

Thus each demand region is convex. Their finite family lies in $\mathbb R^2$, so Helly uses three regions. For three or more demands the assumed local intersections imply a global center; for one or two demands the “at most three” formulation includes the whole family itself. By the contrapositive, an empty total intersection is already empty for at most three demand disks.

For $S_0$, pairwise squared distances are $16,13,13$. All are at most $16=(2+2)^2$, so every pair of radius-two disks intersects. For two disks of equal radius, this criterion follows from the midpoint when the center separation is at most twice the radius, and from the triangle inequality in the other direction. The first two disks here are externally tangent at $(2,0)$. That point fails the third disk since its distance from $(2,3)$ is three. Thus pairwise checks alone accept an infeasible proposal.

Worked solution: optimization. At $c=(2,5/6)$, the squared distances to the first two points are $4+25/36=169/36$; to the third they are $(3-5/6)^2=169/36$. The weights sum to one and have weighted mean $c$. For every $z$, cancel the linear term in the expansion to obtain

$$ \sum_{i=1}^3\lambda_i\|p_i-z\|^2=169/36+\|z-c\|^2. $$

Since a maximum is at least its weighted average, the largest distance from $z$ is at least $13/6$. The proposed center attains that value, proving optimality exactly. This certificate uses all three points with positive weights, and explains the failure at radius two.

Worked solution: incidence proof. There are $k$ choices for $x$ and $2k^2$ for $y$, giving $2k^3$ points. There are $k$ choices of slope and $k^2$ of intercept, giving $k^3$ lines. Different coefficient pairs give different lines because equality of the equations as sets forces both slope and intercept to agree.

For any selected line and any $x\in\{1,\ldots,k\}$, its unique ordinate is the integer $ax+b$. It satisfies

$$ 2\le ax+b\le k\cdot k+k^2=2k^2. $$

Hence it belongs to the declared vertical range. Every line contains exactly one selected point for each of the $k$ possible abscissas, and no other selected points, so exactly $k$ incidences arise per line. Therefore $I=k\cdot k^3=k^4$. The construction is real-plane geometry on integer coordinates; no finite-field wraparound is involved.

For $k=2$, the complete line-by-line table is

Repeated points in different rows represent distinct incidences. There are sixteen points in $P_2$, including some lying on none of the eight selected lines; nevertheless the table contains all sixteen incidences.

Worked solution: exploration and scale. Independent integer enumeration should return

Symbolically, $n^{2/3}m^{2/3}=2^{2/3}k^4$, so the ratio $I/(n^{2/3}m^{2/3})$ is the constant $2^{-2/3}$. Meanwhile $n+m=3k^3$. For large $k$, the incidence count grows faster than the additive terms. Thus the leading scale in the theorem is attained up to a constant on this infinite family, a proof of the scale's necessity in the balanced regime. Four experimental rows alone would not establish that conclusion.

Application and extension. For a single emergency-service site with straight-line service radius $r$, each demand location defines a permissible disk of centers. Helly yields a short certificate for a rejected radius; the weighted boundary-point certificate proves the best attainable worst-case distance. The convex model assumes unrestricted planar placement and Euclidean travel. A road network, obstacles, or multiple service sites changes the feasible sets or the optimization variables and requires a new analysis.

With unequal radii, each permissible set remains a convex disk, so the at-most-three infeasibility certificate survives unchanged. Equal radii were needed for the particular minimum-enclosing-disk objective and its common-boundary-radius identity, not for Helly's theorem itself. This separates the general convexity consequence from the more specialized optimization example.