Computational geometry

Computational geometry is what is left of geometry when the figure refuses to dissolve. On the geometry page the recurring move is reduce before coding: find the algebraic object the picture is secretly describing and compute with that instead. The forty-six problems here are the ones where that move only gets you halfway. You are handed five thousand segments, or fifty thousand cuboids, or thirty-four thousand lattice points, and there is no formula that collapses them — you have to compute on the configuration itself. Sometimes the configuration is not even given: a rule grows it, or the problem asks for the best one that exists, and then you also have to find a representation in which you can build it exactly. The subject is what all of that costs and how to make it exact.

One primitive does almost all the work

Nearly every predicate in this list is the sign of a $2 \times 2$ determinant. For vectors $u$ and $v$, the cross product $u \times v = u_x v_y - u_y v_x$ is twice the signed area of the triangle they span, and its sign is the orientation: positive when $v$ turns counter-clockwise from $u$, negative when clockwise, zero when they are collinear.

def cross(o, a, b):  # sign > 0 left turn, < 0 right turn, 0 collinear
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

That one three-multiplication expression, with no division and no square root, answers the questions these problems actually ask:

question in terms of orientation
is a point inside a triangle? the three directed edges give the same sign
do two segments cross properly? each segment's endpoints straddle the other's line
is this vertex a convex turn? the turn does not bend right
which of two directions is further counter-clockwise? the cross product of the two directions
what is the area of a polygon? the sum of the fan's signed areas

Problem 102 is the primitive in its purest form: a fixed test point at the origin makes each edge test a two-term cross product of vertex coordinates, and containment is "all three share a sign". Problem 165 uses the same determinant twice — once as the denominator that detects parallelism, once as the numerators that locate the crossing. Problem 184 sorts thirty-four thousand lattice points by polar angle and never calls atan2 in the hot path, because "is $P$ within a half turn ahead of $A$?" is cross(A, P) > 0. Problem 252 decides convexity, emptiness and area with nothing else.

The practical consequence is worth stating plainly: learn the orientation test, and refuse to write anything else. A line equation with a slope has a division and a vertical-line special case. A comparison of angles has a transcendental function and a wrap-around at $\pi$. The determinant has neither.

Degeneracy is the problem, not an edge case

The naïve version of any of these algorithms is a page long and takes an afternoon. The correct version is the same page plus a fortnight of arguing about whether an inequality is strict — and that argument is the actual work.

Read the statements closely and you find the boundary conventions are load-bearing, deliberately so. Problem 102 wants the origin strictly interior, so a vertex on an edge must not count. Problem 165 wants proper intersections: shared endpoints, T-junctions and collinear overlaps are all excluded, which is three separate exclusions dressed as one word. Problem 252 permits other points on the perimeter of a hole but not in its interior, so its emptiness comparison is non-strict on one side and strict on the other, and a point lying on an internal diagonal has to be treated differently from a point lying on an edge.

Lattice inputs make this unavoidable rather than theoretical. Among five hundred lattice points, exactly collinear triples do occur; on a grid of radius $105$, $(1,0)$ and $(2,0)$ share a ray, so an angular sort has genuine ties. Problem 184's complement count has to distinguish three collinear cases — same ray (cross $= 0$, dot $> 0$), antipodal (cross $= 0$, dot $< 0$), and everything else — and gets the antipodal ones by a separate inclusion–exclusion argument over primitive directions, because the half-open sweep provably misses them. That is decompose overlap applied to a geometric boundary.

Two habits keep this tractable:

  • Write the convention down before the first line of code. Half-open intervals $[a, b)$, half-open arcs $[\theta, \theta + \pi)$, "strictly inside" versus "on the perimeter" — pick one and make every predicate agree with it. Problem 212's nested sweeps use half-open boxes precisely so that every boundary comparison stays a clean strict inequality.
  • Brute-force the small case. Every one of these problems ships a worked example, and an $O(n^3)$ reference implementation over twenty points will find a sign error that a proof will not. Problem 184's sweep was verified exhaustively against the naïve triple loop before being trusted at $r = 105$. When the small case is the only evidence for a structural guess, it serves as the proof itself and not just a test (see calibrate theory on known answers). Problem 983's whole model rests on an exhaustive search over small radii, which showed every perfect set coming in exactly the sizes the model predicts.

Integers, or a canonical rational — never a float

If a geometric quantity decides a count, it must be exact. This is the domain where exact arithmetic for equality stops being advice and becomes a correctness requirement, because a float that is wrong in the last bit does not produce a slightly wrong answer — it produces a different integer.

Three patterns cover almost every case:

  • Keep the denominator instead of dividing. A segment intersection is $t = t_{\text{num}} / \text{denom}$; normalise the sign so $\text{denom} > 0$ and the interior test $0 < t < 1$ becomes $0 < t_{\text{num}} < \text{denom}$, entirely in integers. No division ever happens.
  • Canonicalise before comparing. When distinctness is the question — problem 165 asks for distinct crossing points, not crossing pairs — represent the point as an integer triple $(n_x, n_y, d)$ meaning $(n_x/d, n_y/d)$, divide through by the gcd, and fix $d > 0$. Equal points then have byte-identical keys and a sort or a hash set deduplicates them exactly. See canonical form.
  • Carry doubled areas. Polygon areas are half-integers; hold twice the area as an integer throughout and halve once at the end. Problem 252's trailing .5 is exact rather than a rounded float because of this.
  • Pack vectors linearly. When the question is "does this sum of vectors equal one of those vectors?", encode $(x, y)$ as the single integer $x \cdot 2^{21} + y$. The map is linear, so the key of a sum is the sum of the keys, and while $|y|$ stays well below $2^{20}$ it is also injective. Problem 983 tests thousands of signed vector sums against a set of lattice vectors this way, using a hash table in C and a sorted NumPy array with searchsorted in Python, and never builds a tuple.

The cost is that intermediate values grow. Cross products of coordinates near $10^5$ are fine in 64 bits; sums of $\binom{34608}{3}$-sized counts, or products of numerators, are not. Problem 184 reaches for __int128 in C and relies on Python's arbitrary-precision integers on the other side — the port's only real asymmetry. Problem 957 makes the same split. Its count grows like $16^n$, and the C port's __int128 holds it only up to $n = 30$, so the port rejects larger inputs instead of wrapping silently. Watch integer width is a standing hazard here, and it is silent when you get it wrong.

Four ways out of the quadratic

The default cost of "consider every pair" is $O(n^2)$ and of "consider every triple" is $O(n^3)$, and the inputs are sized so that one of those is affordable and the next one up is not. The escapes fall into four families.

Sort by angle, then sweep. Ordering is the single most productive preprocessing step in the subject, and the order is almost always angular. Problem 184 turns a two-dimensional containment question into a one-dimensional one — the origin is inside a triangle iff no angular gap between consecutive vertices reaches $\pi$ — then counts the complement with a two-pointer pass over the sorted points, because the arc boundary advances monotonically as the anchor rotates. $\binom{N}{3} \approx 7 \times 10^{12}$ triples become one $O(N \log N)$ sort. Problem 252 sorts each apex's fan by direction so that a chain can only extend forwards, which is exactly the shape a dynamic programming recurrence needs; the emptiness test and the convexity test then both reduce to prefix conditions, settled by running maxima rather than by rescanning.

Sweep a line and lose a dimension. The sweep line turns a $d$-dimensional measure into a stack of $(d-1)$-dimensional ones. Problem 212 — Klee's measure problem in three dimensions — computes a union volume by compressing distinct $x$-coordinates into slabs, measuring each slab's rectangle union by the same trick over $y$, and each of those by merging $z$-intervals. Three nested sweeps, each a dozen lines, no inclusion–exclusion over $2^k$ subsets.

Index space, not pairs. If interactions are local, do not enumerate pairs at all. Problem 212's cuboids have side at most $399$, so bucketing space into a grid index of cells of side $400$ means a cuboid registers in at most eight buckets and can only meet cuboids sharing one. Fifty thousand objects, an average of three overlaps each, and the quadratic never happens. This is size the work to the input in its most literal form: the grid resolution is read off the largest object.

Recurse on structure. When the configuration is generated rather than given, recurse on the generator. Problem 199 fills an Apollonian gasket using the Descartes circle theorem — each gap is identified entirely by its three bounding curvatures, so congruent gaps merge and $3^n$ circles become a handful of distinct states (exploit symmetry). Problem 226 integrates under the blancmange curve by exploiting its self-similarity: on a dyadic interval the curve is a straight chord plus a scaled copy of itself, which gives the integral in closed form and lets a branch-and-bound recursion reach eight decimals in under two hundred interval evaluations. Problem 287's quadtree is the same idea as a data structure: describe the region, not the pixels.

When the configuration is built, not given

In the problems so far the points arrive as input and the degeneracies are hazards to get through. In two of the newer ones the configuration is generated: a rule grows it, or you have to search for an extremal one. The degeneracies then stop being hazards. They become what the problem is about, either the thing to avoid or the thing that must not happen. Both problems are solved the same way: change coordinates until the plane becomes an integer group, at which point every coincidence is an explicit linear relation you can test exactly.

Incidence only? Then the frame is yours to choose. Problem 957 starts from three red and two blue points, and each day it draws every red–blue line and turns each new crossing blue. Only which points lie on which lines matters, so the process is invariant under any projective transformation (projective geometry). Sending the three red points to the coordinate vertices turns their three pencils into the lines $y = c$, $x = c$ and $x/y = c$. A logarithm then turns them into three families of parallel lines, $u = c$, $v = c$ and $u - v = c$. A point turns blue exactly when two of its three coordinates are already present among the blue points, and the concurrent triples drop out by inclusion–exclusion. "Maximal" means general position: every coincidence that geometry does not force has to be absent. The exact way to model that is to give the second blue point multiplicatively independent coordinates, so the reachable values form the free group $\mathbb{Z}^2$ and the process becomes sumsets of integer sets. Random float coordinates would only make accidental coincidences unlikely. The sets grow about fourfold a day, so an exact simulation stops long before the target day. It still produces enough terms for the Berlekamp–Massey algorithm to find a constant-coefficient recurrence and confirm it on the terms it was not fitted to. The final program evaluates the resulting closed form in $O(1)$.

The degeneracies are the constraint. Problem 983 asks for equal circles on lattice centres that meet in lattice points, with as few distinct intersection points as there are circles. Each circle–point incidence is a lattice vector of norm $N = r^2$, so the sum of two squares theorem lists the candidates. Two circles harmonise when their centres differ by $u + v$ with $v \ne \pm u$, and they are tangent when the centres differ by $2u$. The worked example contains the structure that matters: a hypercube projected into the plane. Choose $K$ vectors; their even-weight subset sums are centres and their odd-weight sums are intersection points. The cube fails exactly when some signed sum $\sum \delta_i a_i$ with $\delta \in \{-1, 0, 1\}^K$ equals $0$, $2u$ or a stray $u + v$. Validity is therefore the absence of forbidden linear relations, and a backtracking search can carry the table of all $3^k$ signed sums of its partial choice and kill a branch the moment a relation appears. Symmetry then removes most of the sign choices. Flipping two signs only translates the cube, and flipping one swaps centres with intersection points, so only two signings out of $2^{K-1}$ ever need the expensive exact test.

The two problems turn the degeneracy discussion around. Problems 102–252 must survive collinear triples. Problem 957 must rule out every coincidence that is not forced, and problem 983 must rule out a specific list of them. In both, the work is finding the group in which "these points coincide" is an equation over integers.

When the answer really is a real number

A minority of these problems are genuinely continuous — an area, a crossing time, a threshold index — and there floating point is the right tool. What separates the safe uses from the unsafe ones is not precision but accumulation.

Problem 587 is the model. Fix the radius at $1$ and the L-shaped section has constant area $1 - \pi/4$ for every $n$; only the diagonal's slope varies. The concave sliver's area is then a closed form — a quadratic root, an arcsine, a square root — evaluated once per candidate, and because the ratio is monotone in $n$, finding the least $n$ below a threshold is an exponential bracket plus a bisection, $O(\log n)$ evaluations of an expression whose error is a few ulps. Compare the alternative: numerically integrating a fractal-adjacent region at spacing $2^{-M}$ converges linearly, so eight decimals would want $2^{30}$ samples. Do the calculus symbolically, then evaluate.

The division is clean, and worth deciding before you write anything:

the answer is… arithmetic régime
a count, a set size, an exact area integers or canonical rationals, strict predicates
a real quantity to $k$ decimals closed form evaluated once, error bounded not accumulated

Mixing them is how a provably correct algorithm returns a wrong count.

How to reason about it

  • Reach for orientation first. Before writing a slope, an angle or a line equation, ask whether the sign of a cross product answers the question. It usually does, and it is exact.
  • Fix the boundary convention in writing. Open or closed, strict or non-strict, half-open intervals and half-open arcs — decide once, then make every predicate obey it. Most wrong answers in this domain are off by exactly the degenerate cases.
  • Assume the degeneracies are present. Lattice inputs guarantee collinear triples and shared rays. A pseudo-random generator over a small range guarantees coincident points. Handle them by construction, not by hoping. When the problem asks for the maximum, the opposite holds and general position is what you want. Model it exactly with independent generators, not with random coordinates.
  • Choose the frame when only incidence matters. A projective map, a logarithm or a lattice basis can turn a picture into integer arithmetic in which every coincidence is a linear relation.
  • Sort, then sweep. Angular order is the preprocessing that turns pair enumeration into a linear pass, and it is what makes the two-pointer and prefix-maximum tricks legal.
  • Exploit locality before cleverness. If objects are small relative to the space, a grid bucket beats any asymptotically superior algorithm you were about to implement.
  • Verify against brute force on the statement's example. The naïve $O(n^3)$ version is twenty minutes of work and is the only thing that will catch a sign convention error.
  • Watch the width. Doubled areas, products of numerators and $\binom{N}{3}$ counts overflow 64 bits quietly; check the bound before the port to C, not after.

Problems12 / 44

  • ● 0102 — Triangle Containment
  • ● 0165 — Intersections
  • ● 0184 — Triangles Containing the Origin
  • ● 0199 — Iterative Circle Packing
  • ● 0212 — Combined Volume of Cuboids
  • ● 0226 — A Scoop of Blancmange
  • ● 0252 — Convex Holes
  • ○ 0262 — Mountain Range
  • ○ 0270 — Cutting Squares
  • ○ 0287 — Quadtree Encoding (a Simple Compression Algorithm)
  • ○ 0292 — Pythagorean Polygons
  • ○ 0314 — The Mouse on the Moon
  • ○ 0317 — Firecracker
  • ○ 0392 — Enmeshed Unit Circle
  • ○ 0397 — Triangle on Parabola
  • ○ 0415 — Titanic Sets
  • ○ 0431 — Square Space Silo
  • ○ 0449 — Chocolate Covered Candy
  • ○ 0453 — Lattice Quadrilaterals
  • ○ 0456 — Triangles Containing the Origin II
  • ○ 0460 — An Ant on the Move
  • ○ 0476 — Circle Packing II
  • ○ 0514 — Geoboard Shapes
  • ○ 0525 — Rolling Ellipse
  • ○ 0547 — Distance of Random Points Within Hollow Square Laminae
  • ○ 0562 — Maximal Perimeter
  • ○ 0569 — Prime Mountain Range
  • ● 0587 — Concave Triangle
  • ○ 0604 — Convex Path in Square
  • ○ 0607 — Marsh Crossing
  • ○ 0630 — Crossed Lines
  • ○ 0667 — Moving Pentagon
  • ○ 0695 — Random Rectangles
  • ○ 0702 — Jumping Flea
  • ○ 0742 — Minimum Area of a Convex Grid Polygon
  • ○ 0786 — Billiard
  • ○ 0807 — Loops of Ropes
  • ● 0842 — Irregular Star Polygons
  • ○ 0879 — Touch-screen Password
  • ○ 0897 — Maximal $n$-gon in a region
  • ● 0957 — Point Genesis
  • ○ 0966 — Triangle Circle Intersection
  • ● 0983 — Consonant Circle Crossing
  • ● 0998 — Squaring the Triangle