Geometric Intersection

Bentley-Ottmann Sweep

The Bentley-Ottmann algorithm (1979) computes all $k$ intersection points among $n$ line segments in $O((n + k) \log n)$ time and $O(n)$ space.

Algorithm

Sweep line: a vertical line moves left to right across the plane. At any position, the segments intersecting the sweep line are ordered by $y$-coordinate.

Data structures:

• Event queue (priority queue, ordered by $x$-coordinate): stores left endpoints, right endpoints, and intersection points
• Status structure (balanced BST): stores the segments currently crossing the sweep line, ordered by their $y$-coordinate at the sweep line position

Events:

1. Left endpoint of segment $s$: insert $s$ into the status structure. Check for intersections with its immediate neighbors above and below
2. Right endpoint of segment $s$: remove $s$ from the status structure. Check for intersection between $s$'s former neighbors (they are now adjacent)
3. Intersection point of segments $s_1, s_2$: report the intersection. Swap $s_1$ and $s_2$ in the status structure (their order reverses). Check each with its new neighbor for future intersections

Correctness invariant: an intersection is discovered as an event only when the two segments become adjacent in the status structure. This happens before their actual intersection point (since any "separating" segment must have entered and left between them earlier).

Complexity Analysis

• $O(n + k)$ events total
• Each event processed in $O(\log n)$ time (BST operations)
• Total: $O((n + k)\log n)$ time, $O(n + k)$ space for the event queue (can be reduced to $O(n)$ by discovering intersections lazily)

Space optimization: only store the "next" intersection between adjacent pairs; delete stale events when pairs are separated. This keeps the event queue at $O(n)$ size.

Degeneracies

The original algorithm assumes general position. Practical issues:

• Overlapping segments: treat as a single segment or handle explicitly
• Multiple segments through one point: process all events at the same $x$-coordinate simultaneously; handle the ordering carefully
• Vertical segments: perturb (conceptually rotate slightly) or handle as a special event spanning a $y$-range
• Three segments meeting at a point: the event queue may contain duplicate intersection events; deduplicate

Relation to Arrangement Construction

Bentley-Ottmann computes the arrangement of line segments. The arrangement has $O(n + k)$ vertices, $O(n + k)$ edges, and $O(n + k + 1)$ faces. The sweep implicitly constructs the trapezoidal decomposition.

Red-Blue Intersection

Given two sets of segments (red and blue), find all red-blue intersection pairs (ignoring red-red and blue-blue intersections).

Applications: overlay of two maps/layers, Boolean operations on polygons (edges from different polygons).

Algorithms:

• Modified Bentley-Ottmann: only check intersections between differently colored adjacent segments. Same $O((n + k_{rb}) \log n)$ complexity
• Balaban's algorithm (1995): $O(n \log n + k)$ using a more sophisticated hierarchical approach. Optimal but complex
• Segment tree approach: insert one color into a segment tree, query with the other. $O(n \log n + k)$

For the special case where both sets are non-crossing (e.g., edges of two simple polygons), algorithms achieving $O(n \log n + k)$ are simpler.

Rectangle Intersection

Axis-Aligned Rectangle Intersection

Given $n$ axis-aligned rectangles, find all $k$ intersecting pairs.

Sweep line approach:

1. Create events at left and right edges of each rectangle
2. Sweep left to right; maintain active rectangles (those whose vertical interval is "alive")
3. At each left edge: query active rectangles for those overlapping the new rectangle's $y$-interval; insert the new rectangle
4. At each right edge: remove the rectangle

Using an interval tree or segment tree for the active set: $O(n \log n + k)$ time.

Clarkson-Shor randomized: expected $O(n \log n + k)$ without the sweep.

Rectangle Enclosure

Find all pairs where one rectangle contains another. Reduces to dominance queries: rectangle $R_1$ contains $R_2$ iff $R_1.\text{left} \leq R_2.\text{left}$, $R_1.\text{right} \geq R_2.\text{right}$, and similar for top/bottom. This is a 4D dominance problem, solvable in $O(n \log^2 n + k)$.

Measure of the Union

Compute the area of the union of $n$ rectangles.

Sweep line + segment tree: sweep vertically, maintain the total length of the covered portions of the sweep line using a segment tree with "count" annotations. $O(n \log n)$ time.

Klee's measure problem: generalization to $d$ dimensions. $O(n^{d/2} \log n)$ is the best known for $d \geq 3$ (Chan, 2013). The problem is closely related to depth computation and has connections to circuit complexity lower bounds.

Minkowski Sums

The Minkowski sum of sets $A$ and $B$ is:

$A \oplus B = \{a + b : a \in A, b \in B\}$

Convex Polygons

If $A$ has $n$ vertices and $B$ has $m$ vertices (both convex):

• $A \oplus B$ is convex with at most $n + m$ vertices
• Algorithm: merge the sorted edge sequences of $A$ and $B$ (sort by angle), yielding the edge sequence of $A \oplus B$ in $O(n + m)$ time

Simple Polygons

If $A$ is a simple polygon with $n$ vertices and $B$ is convex with $m$ vertices:

• Decompose $A$ into convex pieces (e.g., triangulation: $O(n)$ pieces)
• Compute Minkowski sum of each piece with $B$: $O(n \cdot m)$ total
• Take the union of all resulting polygons: $O(nm \cdot \alpha(nm) \log^2(nm))$ via arrangement computation

For two non-convex polygons: complexity can be $\Theta(n^2 m^2)$ in the worst case (tight for simple polygons).

Applications

• Collision detection: object $A$ collides with $B$ iff the origin lies in $A \oplus (-B)$ (Minkowski difference). This reduces collision to a point-in-polygon test
• Robot motion planning: configuration space obstacle is the Minkowski sum of the obstacle with the robot's reflection through the origin
• Morphological operations: dilation in image processing is Minkowski sum with a structuring element; erosion is Minkowski difference
• Offsetting: Minkowski sum with a disk gives the offset curve/polygon

Boolean Operations on Polygons

Compute union, intersection, difference, and symmetric difference of polygonal regions.

Weiler-Atherton Algorithm

Classic algorithm for polygon clipping (intersection/union of two simple polygons):

1. Find all intersection points between edges of the two polygons
2. At each intersection, record entry/exit status (entering or leaving the other polygon)
3. Traverse the boundary, switching between polygon boundaries at intersection points:
   • For intersection: follow the clip polygon when entering, subject polygon when exiting
   • For union: follow the outer boundaries

Handles multiple components and holes with careful bookkeeping. $O((n + m + k) \log(n + m))$ where $k$ is the number of intersections.

Sweep-Line Approach (Nef Polygons)

Represent polygons as Nef polygons (closed under all Boolean operations, including complement):

1. Compute the arrangement of all edges from both polygons
2. Label each face of the arrangement with its membership in $A$ and $B$
3. Extract faces satisfying the Boolean condition (e.g., for intersection: faces in both $A$ and $B$)

This is the approach used in CGAL. Handles all degeneracies, multiple components, holes, and unbounded faces. Complexity: $O((n + k) \log n)$ for the arrangement, where $k$ is the number of edge intersections.

Greiner-Hormann Algorithm

Simple algorithm for polygon clipping that handles arbitrary simple polygons (including concave):

1. Insert intersection points into both polygon edge lists
2. Mark intersections as entering/exiting
3. Traverse, collecting output polygons by alternating between input polygons at intersections

Simpler than Weiler-Atherton but struggles with degeneracies (T-intersections, overlapping edges). The Foster-Overfelt variant addresses many degenerate cases.

Vatti's Algorithm

Used in the Clipper library. Handles complex polygons with self-intersections:

• Sweep-line based
• Processes horizontal spans ("scanbeams")
• Supports union, intersection, difference, XOR
• Handles holes, self-intersecting polygons, and floating-point coordinates

The Clipper library (Angus Johnson) and Clipper2 are widely used practical implementations.

Polygon Overlay and Map Operations

Map overlay: given two planar subdivisions (maps), compute their overlay (arrangement of all edges from both maps, with faces inheriting attributes from both input maps).

Algorithm: essentially the Bentley-Ottmann sweep adapted for planar subdivisions:

1. Compute all edge intersections between the two maps
2. Split edges at intersection points
3. Build the combined DCEL (doubly-connected edge list)
4. Assign face attributes by traversing adjacencies

$O((n + k) \log n)$ time. This is a core operation in geographic information systems (GIS).

Segment Intersection Counting and Reporting Lower Bounds

Counting: given $n$ segments, determine the number of intersections.

• $\Omega(n \log n)$ lower bound (even for detecting if any intersection exists, via sorting reduction)
• $O(n^{4/3})$ algorithm exists for counting (without reporting) --- uses multi-level partition trees (Agarwal, 1990)

Reporting: $\Omega(n \log n + k)$ lower bound. The Bentley-Ottmann algorithm nearly matches this (off by a $\log$ factor on $k$).

Optimal: Balaban (1995) achieves $O(n \log n + k)$ for reporting, but the algorithm is significantly more complex than Bentley-Ottmann.

3D Intersection Problems

Triangle-Triangle Intersection

Two triangles in 3D can intersect in a point, a segment, or overlap (coplanar). The Moller algorithm tests intersection in $O(1)$ using orientation predicates:

1. Test if all vertices of triangle 1 are on the same side of triangle 2's plane (and vice versa)
2. If not, compute the intersection of each triangle with the other's plane (a line segment)
3. Test if the two segments overlap

3D Segment-Triangle Intersection

Ray-triangle intersection is fundamental to ray tracing. Moller-Trumbore algorithm: compute barycentric coordinates of the intersection point via Cramer's rule in $O(1)$. The point is inside the triangle iff all barycentric coordinates are in $[0, 1]$.

Bounding Volume Hierarchies (BVH)

For efficient intersection testing among many objects:

• AABB trees: axis-aligned bounding box hierarchy. Fast overlap test (coordinate comparisons only), but loose fit for rotated objects
• OBB trees: oriented bounding boxes. Tighter fit, more expensive overlap test
• Sphere trees: simplest overlap test, but poor fit for elongated objects
• BVH construction: top-down (split by median/SAH), bottom-up (agglomerative), or spatial (binning). Surface area heuristic (SAH) optimizes expected ray traversal cost

SAH cost model: $C(N) = C_{\text{trav}} + p_L \cdot C(N_L) + p_R \cdot C(N_R)$ where $p_L, p_R$ are the probabilities of hitting the left/right child (proportional to surface area). Minimized by greedy splitting.