I use computational geometry whenever I need to design efficient algorithms for problems involving points, lines, polygons, and other geometric objects. I think of this field as the intersection of geometry and algorithm design, where I care not just about geometric correctness but about achieving good asymptotic performance on potentially large sets of geometric data. I find computational geometry essential because so many practical systems — mapping software, computer graphics, robotics, and computer-aided design — reduce to fundamentally geometric questions like “do these shapes intersect?” or “what is the smallest enclosing region for these points?”
History and Background
I trace the formal emergence of computational geometry as a distinct field to the 1970s, with Michael Shamos’s 1978 PhD thesis often cited as foundational, introducing the systematic algorithmic study of geometric problems. I note that earlier geometric algorithm work existed piecemeal — for instance, the gift wrapping algorithm for convex hulls dates to the 1970s as well, developed by R.A. Jarvis in 1973. I see the field mature rapidly through the 1980s with the development of the plane sweep technique by Shamos and Hoey, and Kirkpatrick and Seidel’s optimal convex hull algorithms. I regard the 1985 textbook by Preparata and Shamos, Computational Geometry: An Introduction, as a landmark that consolidated the field’s core results and techniques into a coherent curriculum.
Problem Statement
I use computational geometry to solve problems where I need to efficiently reason about spatial relationships among geometric objects — for example, finding the convex hull of a point set, determining whether two line segments intersect, finding the closest pair of points, or partitioning space for efficient querying. I care about these problems because naive brute-force approaches (checking all pairs of objects, for instance) often scale quadratically or worse, while carefully designed geometric algorithms can achieve much better asymptotic bounds by exploiting spatial structure.
Core Concepts
I rely on these foundational ideas:
- Convex hull: the smallest convex polygon containing a given set of points.
- Cross product / orientation test: determines whether three points make a clockwise, counterclockwise, or collinear turn.
- Line segment intersection: determining whether and where two segments cross.
- Plane sweep: a technique where I move an imaginary line across the plane, processing events (points, segment endpoints) in sorted order.
- Voronoi diagram: a partition of the plane into regions based on proximity to a given set of points.
- Delaunay triangulation: a triangulation maximizing the minimum angle of triangles, dual to the Voronoi diagram.
How It Works
When I approach a computational geometry problem, I follow this general process:
- I identify the geometric objects involved (points, segments, polygons) and the specific relationship or property I need to compute.
- I choose a representation for these objects (coordinate pairs, doubly connected edge lists, etc.).
- I select an algorithmic paradigm suited to the problem — sorting-based approaches (for convex hull), divide-and-conquer (for closest pair), or plane sweep (for segment intersection).
- I implement geometric primitives carefully (orientation tests, distance calculations), since these are the building blocks every higher-level algorithm depends on.
- I combine primitives according to the chosen algorithm, processing objects in a specific order (sorted by angle, by x-coordinate, or by sweep-line event) to achieve the target time complexity.
Working Principle
I understand the internal logic of most computational geometry algorithms as exploiting sorted order and incremental processing to avoid redundant pairwise checks. For example, the plane sweep technique works because I only need to compare objects that are “close” to the current sweep line position at any given moment, rather than comparing every pair of objects globally — this locality is what allows algorithms like Bentley-Ottmann segment intersection to run in $O((n + k)\log n)$ instead of the naive $O(n^2)$. Convex hull algorithms similarly rely on the geometric fact that hull vertices, when sorted by angle or x-coordinate, form a predictable turning pattern (all left turns or all right turns), which I can verify incrementally using the cross product.
Mathematical Foundation
I define the cross product of vectors $\vec{OA}$ and $\vec{OB}$ (used for orientation tests) as:
$$ \vec{OA} \times \vec{OB} = (A_x – O_x)(B_y – O_y) – (A_y – O_y)(B_x – O_x) $$
I interpret the sign of this value: positive indicates a counterclockwise turn, negative indicates clockwise, and zero indicates collinearity.
I define the Euclidean distance between two points, used in closest-pair algorithms:
$$ d(P, Q) = \sqrt{(P_x – Q_x)^2 + (P_y – Q_y)^2} $$
I state the Graham Scan convex hull algorithm’s core loop invariant: at every step, the hull points processed so far form a convex polygon, maintained by popping the stack whenever the last three points make a non-counterclockwise turn:
$$ \text{cross}(P_{k-2}, P_{k-1}, P_k) \le 0 \implies \text{pop } P_{k-1} $$
I state the key recurrence for the closest-pair divide-and-conquer algorithm:
$$ T(n) = 2T(n/2) + O(n) $$
which, by the Master Theorem, resolves to:
$$ T(n) = O(n \log n) $$
I justify the linear merge step ($O(n)$) in this recurrence by proving that within the “strip” of width $2\delta$ around the dividing line (where $\delta$ is the minimum distance found so far in the two halves), I only need to compare each point against at most 7 other points ahead of it in sorted $y$-order, a geometric packing argument that bounds the number of points that can fit within a $\delta \times 2\delta$ rectangle without violating the minimum distance $\delta$.
Diagrams
flowchart TD
A[Set of points/segments as input] --> B[Sort by angle, x-coordinate, or build event queue]
B --> C{Algorithm type}
C -->|Convex Hull| D[Process points, maintain hull using orientation test]
C -->|Closest Pair| E[Divide and conquer, check strip near midline]
C -->|Segment Intersection| F[Sweep line, process events in order]
D --> G[Return final geometric structure]
E --> G
F --> G
Pseudocode
I write pseudocode for the Graham Scan convex hull algorithm:
function GRAHAM_SCAN(points):
p0 = point with lowest y-coordinate (leftmost if tie)
sort remaining points by polar angle relative to p0
stack = [p0, points[0], points[1]]
for i from 2 to length(points) - 1:
while size(stack) > 1 and
cross(secondTop(stack), top(stack), points[i]) <= 0:
pop(stack)
push(stack, points[i])
return stack // the stack now contains the convex hull vertices in order
Step-by-Step Example
I compute the convex hull of the points: $A(0,0)$, $B(2,0)$, $C(2,2)$, $D(0,2)$, $E(1,1)$.
- I select $p_0 = A(0,0)$ as the point with the lowest $y$-coordinate.
- I sort the remaining points by polar angle from $A$: $B(2,0)$, $E(1,1)$, $C(2,2)$, $D(0,2)$.
- I initialize the stack with $A, B, E$.
- I check the turn from $A \to B \to E$: this is a left turn (counterclockwise), so I keep it and push $C$: stack is $A, B, E, C$.
- I check the turn from $B \to E \to C$: I compute this as a right turn (clockwise, since $E$ is interior), so I pop $E$: stack is $A, B, C$.
- I push $D$: I check the turn $B \to C \to D$, a left turn, so I keep $D$: stack is $A, B, C, D$.
I obtain the final convex hull: $A(0,0), B(2,0), C(2,2), D(0,2)$ — correctly excluding the interior point $E(1,1)$.
Time Complexity
I analyze the Graham Scan convex hull algorithm as $O(n \log n)$ overall — dominated by the initial angular sort, since the scanning phase itself runs in $O(n)$ amortized time (each point is pushed and popped from the stack at most once). I analyze the closest-pair divide-and-conquer algorithm as $O(n \log n)$ as well, per the recurrence solved above. I note that the naive brute-force approach to either problem (checking all pairs for closest pair, or checking all triples for hull membership) runs in $O(n^2)$ or worse, which is precisely why the specialized geometric algorithms matter for large inputs. These bounds represent worst-case behavior; best and average cases for these particular algorithms do not differ asymptotically, since the sorting step dominates regardless of point configuration.
Space Complexity
I require $O(n)$ space for both the Graham Scan (to store the sorted points and the hull stack) and the closest-pair algorithm (to store the recursive point sets and the strip array during merging). Plane sweep algorithms for segment intersection typically require $O(n + k)$ space, where $k$ is the number of intersection points found, since I maintain an event queue and a sweep-line status structure alongside the output.
Correctness Analysis
I justify Graham Scan’s correctness by the loop invariant that the stack always represents a convex polygon over the points processed so far: each time I add a new point, I first remove any points that would create a non-left turn (a reflex angle), guaranteeing the hull property is preserved. Since I process points in angular order around $p_0$, every point that should belong to the hull gets a chance to be added, and every point that lies “inside” relative to its neighbors gets correctly popped. I justify the closest-pair algorithm’s correctness by structural induction on the divide-and-conquer recursion: I assume the recursive calls correctly find the minimum distance within each half, and I prove that the merge step correctly checks the only remaining possibility — a closest pair straddling the dividing line — by scanning the narrow strip described in the Mathematical Foundation section.
Advantages
- I achieve significant asymptotic speedups ($O(n \log n)$) over brute-force ($O(n^2)$ or worse) approaches for many core geometric problems.
- Geometric algorithms generalize well, forming reusable primitives (orientation tests, distance calculations) that combine to solve more complex problems.
- Plane sweep and divide-and-conquer paradigms transfer to a wide range of related geometric problems beyond the original use case.
- Many computational geometry algorithms have elegant, verifiable correctness proofs rooted in provable geometric properties.
Disadvantages
- I find that geometric algorithms are notoriously sensitive to floating-point precision issues, where small numerical errors can cause incorrect orientation tests or missed intersections.
- Implementing robust geometric predicates (handling degenerate cases like collinear points) is more intricate than the basic algorithmic idea suggests.
- Some higher-dimensional geometric problems (beyond 2D/3D) suffer from the curse of dimensionality, making efficient algorithms much harder to design.
- Certain geometric data structures (like fully dynamic Voronoi diagrams) are complex to implement and maintain efficiently under insertions and deletions.
Applications
I apply computational geometry in:
- Geographic Information Systems (GIS): point-in-polygon tests, map overlay, and spatial indexing.
- Computer graphics: collision detection, visibility determination, and mesh generation.
- Robotics: motion planning and obstacle avoidance using configuration space geometry.
- Computer-aided design (CAD): geometric modeling and boundary representation of 3D objects.
- Wireless networking: Voronoi diagrams model coverage regions for cell towers.
- Machine learning: nearest-neighbor search and clustering rely on geometric proximity structures like k-d trees.
Implementation in C
I implement the orientation test and a basic convex hull check using the gift wrapping (Jarvis March) idea for a small point set, with comments:
#include <stdio.h>
typedef struct {
int x, y;
} Point;
// I compute the cross product to determine orientation of triplet (O, A, B)
// Positive: counterclockwise, Negative: clockwise, Zero: collinear
long cross(Point O, Point A, Point B) {
return (long)(A.x - O.x) * (B.y - O.y) - (long)(A.y - O.y) * (B.x - O.x);
}
int main() {
Point points[] = {{0,0}, {2,0}, {2,2}, {0,2}, {1,1}};
int n = 5;
// I find the point with the lowest y-coordinate (leftmost if tie)
int start = 0;
for (int i = 1; i < n; i++) {
if (points[i].y < points[start].y ||
(points[i].y == points[start].y && points[i].x < points[start].x)) {
start = i;
}
}
printf("Starting hull point: (%d, %d)\n", points[start].x, points[start].y);
// I demonstrate the orientation test on a sample triplet
Point O = points[0], A = points[1], B = points[4];
long orientation = cross(O, A, B);
if (orientation > 0) {
printf("Turn from O->A->B is counterclockwise\n");
} else if (orientation < 0) {
printf("Turn from O->A->B is clockwise\n");
} else {
printf("Points O, A, B are collinear\n");
}
return 0;
}
Sample Input and Output
I hardcode the point set $A(0,0), B(2,0), C(2,2), D(0,2), E(1,1)$ from the walkthrough, and I expect:
Starting hull point: (0, 0)
Turn from O->A->B is clockwise
Optimization Techniques
- I use k-d trees or range trees to accelerate nearest-neighbor and range-query operations from $O(n)$ per query down to $O(\log n)$ after preprocessing.
- I apply rotating calipers technique to solve problems like finding the diameter of a convex polygon in $O(n)$ time after the hull is computed.
- I use fortune’s algorithm (a specialized plane sweep) to construct Voronoi diagrams in optimal $O(n \log n)$ time.
- I apply exact arithmetic or carefully designed epsilon-tolerant comparisons to mitigate floating-point robustness issues in orientation tests.
- I use spatial partitioning structures (quad-trees, grids) to reduce the number of pairwise geometric checks needed in collision detection systems.
Common Mistakes
- I sometimes forget to handle collinear points as a special case in convex hull algorithms, leading to incorrect hull boundaries.
- I use floating-point equality checks directly for geometric predicates instead of epsilon-tolerant comparisons, causing subtle bugs from precision errors.
- I mismanage the sorting step in Graham Scan, forgetting to break angular ties by distance from the starting point, which can corrupt the scan.
- I forget to consider the “0/1 point” edge cases (empty input, single point, or all collinear points) when implementing geometric algorithms.
- I assume 2D geometric intuition transfers directly to 3D problems without adjustment, missing important differences in complexity and predicate design.
Further Reading
- de Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. Computational Geometry: Algorithms and Applications: https://link.springer.com/book/10.1007/978-3-540-77974-2
- Preparata, F. P., & Shamos, M. I. Computational Geometry: An Introduction: https://link.springer.com/book/10.1007/978-1-4612-1098-6
- O’Rourke, J. Computational Geometry in C: https://www.cs.jhu.edu/~misha/Spring20/ORourke98.pdf
- CGAL (Computational Geometry Algorithms Library) documentation: https://www.cgal.org/
- Shamos, M. I. (1978). “Computational Geometry” PhD Thesis, Yale University: https://www.cs.cmu.edu/~shamos/
