Geometry Basics: Orientation, Line Sweep, Closest Pair

A geometric picture is useful intuition, but an implementation needs exact rules for endpoints, ties, and large coordinates. This module turns three pictures into testable invariants: a signed turn for segment intersection, an active count for interval overlap, and a shrinking distance bound for closest pair.

You should know sorting, merge sort, and basic divide-and-conquer. Work through the intersection exercise first, then the sweep, then closest pair. At the end you should be able to predict degenerate cases, derive the merge step, and explain why the arithmetic fits the declared input range.

1. Orientation replaces slope calculations

For A=(ax,ay), B=(bx,by), and C=(cx,cy), compute

orient(A,B,C) = (bx-ax)*(cy-ay) - (by-ay)*(cx-ax)

Positive means a counterclockwise turn from AB toward AC; negative means clockwise; zero means collinear. For A=(1,1), B=(4,1), C=(2,3), the result is 3*2 - 0*1 = 6. No division is needed, so vertical lines work without a special slope value.

For two closed segments AB and CD, compute four orientations: C and D relative to AB, then A and B relative to CD. A proper crossing has opposite nonzero signs in both pairs. Testing only one pair checks the infinite line through one segment and can accept an intersection outside the other segment.

Zero needs a separate rule. If orient(A,B,C)==0, C lies on AB only when both its coordinates are within the inclusive coordinate bounds of A and B:

min(ax,bx) <= cx <= max(ax,bx)
min(ay,by) <= cy <= max(ay,by)

Check each of the four collinear-endpoint possibilities, then the strict opposite-sign test. This handles horizontal/vertical segments, endpoint contact, overlap, and zero-length segments with the same rules.

Segments on the x-axis	Orientations	Bounding check	Intersect?
[0,2] and [3,5]	All zero	No endpoint in the other	No
[0,2] and [2,5]	All zero	Shared endpoint 2	Yes
[0,4] and [1,3]	All zero	Endpoints 1 and 3 inside	Yes
[2,2] and [0,4]	All zero	Point 2 inside	Yes

Predict: AB=(0,0)→(2,0), CD=(3,-1)→(3,1). C and D lie on opposite sides of AB's line, but A and B lie on the same side of CD's line. The segments do not intersect.

Each test takes constant time and space. Compare orientation signs directly; multiplying two orientation values to test o1*o2 < 0 can overflow even when each value fits.

2. Interval overlap: define what happens at a tie

The exercise uses inclusive intervals [start,end] with integer endpoints. At x, an interval beginning at x and one ending at x both count. There are two valid event conventions; use one consistently.

Closed-endpoint events: emit (start,+1) and (end,-1). Sort by coordinate, processing starts before ends at the same coordinate. Track the largest active count after each start. This also works for real-valued endpoints.

Integer successor events: emit (start,+1) and (end+1,-1). An interval contributes at its end and is removed at the next integer. Group all deltas at a coordinate, apply the sum, and record the maximum. The references use successor events and process removals before additions at ties; this avoids artificial intermediate peaks and gives the same maximum. The end+1 representation relies on integer endpoints and an addition that fits the chosen type.

Trace [1,3], [3,3], [3,5] using grouped successor events:

Coordinate	Combined delta	Active after applying it
1	+1	1
3	+2	3
4	-2	1
6	-1	0

The maximum is 3 at x=3. Removing the first interval at 3 would miss that shared endpoint. Empty input has no events and returns zero. Sorting 2n events costs O(n log n) time and O(n) storage.

Reconstruct: for [1,2] and [3,4], successor removal and insertion both occur at 3. Their combined delta is zero; the maximum stays 1. Processing that insertion first and recording the transient count would falsely report 2.

3. Closest pair: what recursion must return

Return the minimum squared distance between two distinct input entries:

distance2(P,Q) = (px-qx)^2 + (py-qy)^2

Two entries may share coordinates, giving distance zero. With fewer than two entries, this exercise returns zero by convention. The answer is squared distance: displacement (3,4) produces 25, not 5.

Checking every pair costs O(n²), too much for 200,000 points. Sort once by (x,y) and split the sequence into halves by index, even when x values tie. Remember the split x-coordinate before recursive calls reorder points.

Each recursive call has two outputs: the smallest squared distance in its subset, and that subset sorted by y. For two or three points, check all pairs and sort those few points by y. For a larger subset:

1. Recurse on its left and right halves. Let d2 be the smaller returned squared distance.
2. Merge their y-sorted outputs in linear time, as in merge sort.
3. Any improvement must cross the split. Keep only points with (x-splitX)^2 < d2; they form the vertical strip in y order.
4. For each strip point, scan later points until (laterY-currentY)^2 >= d2. Beyond that point the vertical distance alone rules out an improvement. Update d2 from candidate pairs.
5. Return the best d2 and the merged y order to the parent.

If d2 reaches zero, no improvement is possible, though the caller still needs the y-sorted output. Do not replace a child's no-pair result with zero inside a general recursion: use infinity internally. The supplied split/base-case structure invokes child calls only on subsets with at least two points.

A crossing pair the children cannot see

Use sorted points (-4,0), (-1,3), (1,3), (5,0). The left child returns 18 and the right child returns 25, so initially d2=18. The split coordinate is 1. The strip contains (-1,3), (1,3), (5,0), because their squared x-distances from 1 are 4, 0, and 16. Its y order starts with (5,0).

The first candidate distances do not improve 18. Comparing (-1,3) with (1,3) gives 4, the final answer. Returning only min(left,right) would incorrectly return 18. The merge step must consider cross-boundary pairs.

Why the strip scan is linear

Write δ = sqrt(d2) for the proof only; the implementation keeps squared integers. Each half has no pair closer than δ. For any strip point, a useful later point lies within a rectangle of width 2δ and height δ. Split each half of that rectangle into four squares of side δ/2. Two points belonging to the same half cannot occupy one square, because its diagonal is shorter than δ. Thus only a constant number of candidates fit; the usual bound is the next seven points in y order. Points on the split retain their original half membership even when x coordinates tie.

The loop's y-distance stop encodes the geometric condition directly; the packing argument bounds how much work it can perform. It does not justify comparing seven neighbors in arbitrary input or x order. The Princeton divide-and-conquer notes illustrate this strip argument.

Merging y order gives T(n)=2T(n/2)+O(n), hence O(n log n) total time and O(n) peak auxiliary space. Sorting the strip from scratch at every recursive node changes the bound to O(n log² n).

4. Make the integer contract part of the algorithm

Coordinates lie in [-10^9,10^9], so a difference can be 2*10^9, its square 4*10^18, and a squared distance as large as 8*10^18. Signed 64-bit integers fit these values. They also fit the conservative 8*10^18 bound for the difference of the two cross-product terms. In Go, convert coordinates to int64 before differences and multiplication. Python integers grow as needed.

The initial minimum must exceed every valid candidate. 1<<62 is about 4.61*10^18, too small: the legal pair (-10^9,-10^9) and (10^9,10^9) has squared distance 8*10^18. Initialize from a real pair or use a suitable 64-bit maximum. Avoid floating-point square roots in the strip test and avoid multiplying orientation signs together.

Before coding, predict results for disjoint collinear segments, a point segment, three intervals meeting at one endpoint, duplicate points, a closest pair straddling the split, and the two extreme-coordinate points. These expose different invariants; passing only ordinary diagonal intersections or nearby point pairs does not check the full contract.