Computational Geometry

Algorithms for solving geometric problems involving points, lines, polygons, and higher-dimensional objects. These techniques power computer graphics, robotics, GIS systems, CAD software, and computational physics—any application where spatial relationships matter.

Intermediate to Advanced

• Basic geometric primitives: Intermediate
• Convex hull and sweep algorithms: Intermediate to Advanced
• Advanced structures (Voronoi, BSP trees): Advanced
• Computational topology: Advanced

The geometry of everything: The physical world is inherently geometric. Any system that interacts with space needs geometric algorithms:

• Robotics: Path planning requires navigating around obstacles (visibility graphs, motion planning)
• Computer graphics: Rendering 3D scenes requires hidden surface removal, ray tracing, collision detection
• GIS and mapping: Finding nearest neighbors, computing map overlays, route planning
• VLSI design: Placing components on chips, routing wires without intersections
• Computer vision: Object recognition, 3D reconstruction from images
• Computational biology: Protein structure analysis, molecular docking

War Story - The Convex Hull in Computer Graphics: In the 1970s, rendering 3D graphics was painfully slow. Computing the convex hull of point sets enabled quick rejection of points interior to objects—dramatically speeding up rendering. Today, every game engine and 3D modeling tool uses convex hull algorithms for collision detection, shadow volumes, and mesh simplification. A simple O(n log n) algorithm unlocked interactive 3D graphics.

War Story - GPS and Voronoi Diagrams: When you search “nearest coffee shop,” the algorithm uses geometric data structures to efficiently answer nearest-neighbor queries. Voronoi diagrams partition space by proximity—each region contains all points closest to a given location. This enables O(log n) nearest-neighbor queries in systems managing millions of locations. Without these structures, every search would require checking all locations—making real-time navigation impossible.

1. Point-line relationships - Which side of line? On line? Distance to line?
2. Line segment intersection - Do two segments intersect? Where?
3. Polygon containment - Is point inside polygon? (ray casting, winding number)
4. Area computations - Polygon area, triangle orientation
5. Cross product and orientation tests - Fundamental primitive for many algorithms

6. Convex Hull - Graham scan O(n log n), Jarvis march O(nh), QuickHull, divide-and-conquer
7. Line Segment Intersection - Bentley-Ottmann sweep line O((n+k) log n) for n segments, k intersections
8. Closest Pair of Points - Divide-and-conquer O(n log n)
9. Triangulation - Polygon triangulation, Delaunay triangulation
10. Point Location - Trapezoidal decomposition, persistent search trees

11. Voronoi Diagrams - Nearest-neighbor partitioning, Fortune’s sweep O(n log n)
12. Delaunay Triangulation - Dual of Voronoi, optimal triangulation properties
13. Range Searching - k-d trees, range trees, orthogonal range queries
14. Binary Space Partitioning (BSP) - Hierarchical space decomposition for graphics
15. Arrangement of Lines - Computing all line intersections, zone theorem
16. Geometric Optimization - Smallest enclosing circle, largest empty circle
17. Motion Planning - Configuration space, visibility graphs, Minkowski sums

• Required:

  • Strong understanding of basic geometry
  • Proficiency with vectors, cross products, dot products
  • Sorting algorithms
  • Basic data structures (trees, heaps)
  • Divide-and-conquer paradigm

• Helpful:

  • Linear algebra (for higher dimensions)
  • Graph algorithms (for motion planning)
  • Basic calculus (for some optimizations)
  • Understanding of geometric transformations

Setup: You have a set of points in the plane (imagine nails on a board). You stretch a rubber band around them and let it snap tight. What shape does it form?

The answer: The convex hull—the smallest convex polygon containing all points.

Why we care: This shape comes up everywhere:

• In graphics: Quick bounding shape for objects
• In statistics: Outlier detection
• In pattern recognition: Shape analysis
• In manufacturing: Material cutting optimization

First attempt - Jarvis March (Gift Wrapping): Start at leftmost point. Find the point that makes the smallest counterclockwise angle with current edge. This is the next hull vertex. Repeat until back at start.

Complexity: O(nh) where h is hull size. Great when h is small!

Better - Graham Scan: Sort points by polar angle from bottommost point. Scan through, maintaining hull by checking if we turn left or right at each point. Right turns mean the middle point isn’t on the hull.

Complexity: O(n log n) always. Sorting dominates.

The insight: Two different approaches! One better for small hulls, one better worst-case. Understanding the tradeoff is crucial.

Setup: You’re designing a security system for an art gallery (a polygon). Where should you place cameras so every point in the gallery is visible from at least one camera?

Theoretical result: For a polygon with n vertices, ⌊n/3⌋ cameras always suffice and sometimes necessary.

Proof approach:

1. Triangulate the polygon
2. Create a graph where vertices are triangles, edges connect adjacent triangles
3. This forms a tree! Color it with 3 colors
4. Place cameras at vertices of most common color

Beautiful connection: Computational geometry + graph theory + combinatorics.

Practical challenge: Finding optimal placement is NP-hard! But the theoretical bound gives us a starting point.

Real application: This isn’t just academic—wireless sensor placement, lighting design, and surveillance systems all face variants of this problem.

Setup: You’re building a video game with hundreds of moving objects. How do you efficiently detect which objects collide?

Naive approach: Check every pair. O(n²) comparisons. Too slow for n=1000!

Insight 1 - Bounding volumes: Wrap each complex object in simple bounding shape (sphere, axis-aligned box). Quick reject most pairs.

Insight 2 - Spatial decomposition: Divide space into grid or tree structure. Only check objects in same or nearby cells.

Insight 3 - Sweep and prune: Sort objects by x-coordinate. Only pairs with overlapping x-ranges can collide. Maintain sorted list as objects move.

The synthesis: Modern game engines use hierarchical bounding volumes (trees of spheres or boxes) combined with spatial hashing. This reduces O(n²) to nearly linear in practice.

The lesson: Computational geometry isn’t about finding THE algorithm—it’s about combining techniques to handle real constraints.

Setup: You have a database of 1 million locations. User clicks on map—find the 10 nearest coffee shops instantly.

Naive: Compute distance to all 1 million locations, sort. O(n log n) per query. Way too slow.

Insight - Voronoi diagram: Preprocess: Partition plane so each cell contains all points closest to one location. Now finding nearest neighbor means: find which cell contains query point!

How to find cell: Point location in planar subdivision. O(log n) with trapezoidal decomposition or persistent search tree.

Total: O(n log n) preprocessing, O(log n) per query. Million locations? No problem!

Extension - k nearest neighbors: Use Voronoi diagram + local search, or build k-d tree for O(k log n) queries.

Real impact: Every mapping app, location-based service, and spatial database uses these structures. Geometric algorithms enable real-time spatial queries on massive datasets.

Spatial reasoning formalized: Humans naturally reason about space, but informally. Computational geometry formalizes spatial intuitions:

• Orientation: “Is this point left or right of this line?” → sign of cross product
• Proximity: “What’s nearby?” → Voronoi diagrams and spatial trees
• Enclosure: “Is this inside?” → ray casting algorithm
• Visibility: “Can I see it from here?” → visibility graphs

These formalizations help us think precisely about space and automate spatial reasoning.

The algorithm:

1. Find point with lowest y-coordinate (break ties by x)
2. Sort all other points by polar angle from this point
3. Push first 3 points onto stack
4. For each remaining point:
   • While stack has ≥2 points and we make a right turn: pop stack
   • Push current point

Why it works: We process points in angular order. Right turns mean the middle point is inside the hull—remove it.

Complexity: O(n log n) from sorting. Scan is O(n) since each point pushed/popped once.

Implementation detail: Cross product determines turn direction. If cross product of vectors (p₁→p₂) and (p₂→p₃) is positive, we turn left. Negative means right turn.

Problem: Find all intersection points among n line segments.

Naive approach: Check all pairs. O(n²) time, even if there are 0 intersections!

Sweep line approach: Imagine a vertical line sweeping left to right across the plane.

• Event points: Segment endpoints and intersection points
• Sweep status: Segments currently intersecting sweep line, ordered by y-coordinate
• Key invariant: Adjacent segments in sweep order are the only candidates for intersection “soon”

The algorithm:

1. Initialize event queue with all segment endpoints
2. Process events in x-order:
   • Segment starts: insert into sweep status, check new neighbors
   • Segment ends: remove from status, check former neighbors
   • Intersection: report it, swap segments, check new neighbors

Complexity: O((n+k) log n) where k = number of intersections. Optimal!

Why it’s clever: We only check segments that are currently “close” in y-coordinate. The sweep line maintains this dynamically.

Fortune’s Algorithm (sweep line approach):

Intuition: Instead of sweep line, use sweep parabola. The parabola consists of points equidistant from sweep line and each site seen so far.

Key structures:

• Beach line: The evolving parabola boundary
• Event queue: Site events (new sites encountered) and circle events (beach line arcs disappear)

The algorithm:

1. Process events in y-order (sweep top to bottom)
2. Site event: Add new arc to beach line
3. Circle event: Remove arc (it’s squeezed to nothing), create Voronoi vertex
4. Maintain doubly-connected edge list for Voronoi diagram

Complexity: O(n log n) time, O(n) space

Why it’s beautiful: The sweep transforms a 2D spatial problem into 1D sequential processing!

Structure: Binary space partitioning tree. At each level, split along different dimension.

• Root: split by x-coordinate
• Level 1: split by y-coordinate
• Level 2: split by x-coordinate again
• Alternate dimensions cyclically

Construction: O(n log n) if built carefully (median-finding at each level)

Range query: Find all points in rectangle. O(√n + k) where k = output size.

Nearest neighbor: O(log n) expected time with good heuristics, but worst-case can be O(n).

When to use: Low dimensions (2D, 3D work well). Higher dimensions suffer “curse of dimensionality.”

• de Berg et al: “Computational Geometry: Algorithms and Applications” - The standard textbook, clear and comprehensive
• O’Rourke: “Computational Geometry in C” - Practical focus with complete implementations
• Preparata & Shamos: “Computational Geometry” - Classic mathematical treatment
• Skiena §17 - Practical introduction with war stories on geometric algorithms

• Stanford CS 268 (Guibas) - Classic computational geometry course
• MIT 6.850 Geometric Folding Algorithms (Demaine) - Advanced topics
• CGAL (Computational Geometry Algorithms Library) - Production-quality C++ implementations

• Shamos & Hoey (1976): Line segment intersection
• Fortune (1987): Sweep line algorithm for Voronoi diagrams
• Guibas & Stolfi (1985): Primitives for subdivision computation
• Chazelle (1991): Triangulating simple polygons in linear time

• Divide-and-Conquer: Closest pair, convex hull variants use geometric recursion
• Computational Topology: Persistent homology, shape analysis
• Graph Algorithms: Visibility graphs, Delaunay triangulations are graphs
• Optimization: Many geometric problems reduce to LP/convex optimization
• Randomized Algorithms: Randomized incremental construction for Voronoi, BSP trees
• Data Structures: Range trees, k-d trees, persistent structures for point location
• Computer Graphics: Nearly all rendering algorithms use geometric primitives
• Machine Learning: Nearest neighbors, clustering algorithms rely on geometric structures

1. Convex Hull Visualizer

   • Implement multiple algorithms: Graham scan, Jarvis march, QuickHull
   • Visualize step-by-step execution
   • Compare performance on different point distributions
   • Add 3D convex hull computation

2. Collision Detection System

   • Build hierarchical bounding volume tree (spheres or AABBs)
   • Implement broad-phase (spatial hashing or sweep-and-prune)
   • Add narrow-phase with exact polygon intersection
   • Benchmark with increasing numbers of objects

3. Voronoi Diagram Generator

   • Implement Fortune’s sweep line algorithm
   • Visualize beach line and event processing
   • Add k-nearest neighbor queries
   • Extend to 3D (Voronoi cells as polyhedra)

4. Robot Path Planning

   • Build visibility graph from polygon obstacles
   • Find shortest path around obstacles
   • Implement Minkowski sum for robot with size
   • Visualize configuration space

5. GIS Query System

   • Build k-d tree or R-tree for spatial indexing
   • Implement range queries (find all points in rectangle)
   • Add nearest neighbor search
   • Benchmark with real geographic datasets

6. Art Gallery Solver

   • Triangulate polygon
   • 3-color the dual graph
   • Visualize guard placement
   • Explore heuristics for near-optimal solutions

2-4 lectures depending on depth

• 1 lecture: Geometric primitives, convex hull (Graham scan), line intersection
• 2 lectures: + Closest pair, triangulation, point location basics
• 3 lectures: + Voronoi diagrams, Delaunay triangulation, range searching (k-d trees)
• 4 lectures: + BSP trees, motion planning, arrangement of lines, advanced topics

1. “Floating point doesn’t matter”

   • FALSE! Geometric algorithms are notoriously sensitive to numerical errors. The “point on line” predicate can fail due to rounding. Robust geometric computing requires careful handling of degeneracies and numerical precision.

2. “Convex hull is always O(n log n)”

   • FALSE! Output-sensitive algorithms like Jarvis march run in O(nh) where h is hull size. When h is small (O(1)), this is O(n)—better than sorting!

3. “Point-in-polygon is expensive”

   • FALSE! Ray casting is O(n) for simple polygon, but with preprocessing (trapezoidal decomposition), queries are O(log n). The right data structure matters.

4. “3D geometry is just 2D with an extra coordinate”

   • FALSE! Many problems jump in complexity: 2D convex hull is O(n log n), but 3D is O(n log n) with more complex algorithms. Higher dimensions get exponentially harder.

5. “Voronoi diagrams are just for nearest neighbors”

   • FALSE! Voronoi diagrams reveal structure about point distributions: clustering, coverage, territory boundaries. They’re used in crystallography, epidemiology, territory planning, and countless other fields.

Computer graphics and games:

• Collision detection and physics engines
• Hidden surface removal (BSP trees, painter’s algorithm)
• Ray tracing and photorealistic rendering
• Mesh generation and simplification

Robotics and motion planning:

• Path planning around obstacles
• Configuration space computation
• Visibility-based planning
• Multi-robot coordination

Geographic Information Systems (GIS):

• Map overlay (intersection of polygonal regions)
• Proximity analysis (Voronoi diagrams)
• Route planning and network analysis
• Terrain analysis and viewshed computation

Manufacturing and CAD:

• VLSI layout and routing
• Sheet metal cutting optimization
• NC machining tool paths
• Assembly planning

Computer vision:

• Feature matching and tracking
• 3D reconstruction from images
• Object recognition via shape matching
• Image segmentation

Computational biology:

• Protein structure analysis
• Molecular surface computation
• Drug docking simulations
• Phylogenetic tree visualization

Traditional (banking model):

“Here’s the convex hull definition. Here’s Graham scan. Step 1: sort by angle. Step 2: scan with stack. Memorize the algorithm.”

Problem-posing approach:

“You have points scattered on a plane. Imagine stretching a rubber band around them—what shape forms? Why do we care about this shape? How would you compute it? Let’s try wrapping around from one point… that’s Jarvis march! Can we do better? What if we process points in a clever order…”

The difference: Students discover WHY the problem matters (bounding shapes, graphics, manufacturing), develop intuition for multiple approaches, and understand the tradeoffs rather than memorizing a single algorithm.

Curriculum placement:

• Week 5-7 for graduate courses (after divide-and-conquer, before/during advanced topics)
• Can be standalone special topics course
• Often paired with computer graphics or robotics courses

Prerequisites check: Students need solid understanding of:

• Divide-and-conquer (closest pair uses it)
• Vectors and cross products (fundamental to all algorithms)
• Sweep line paradigm (similar to event-driven simulation)

Why this timing: Computational geometry provides concrete applications of abstract techniques. It’s also relatively self-contained—doesn’t require extensive background in other algorithms topics.

Ubiquity of spatial data:

• Billions of GPS-enabled devices generating location data
• 3D scanning and modeling becoming routine
• Autonomous vehicles navigating real-world geometry
• VR/AR requiring real-time geometric computation

Algorithmic foundations still relevant: Despite decades of research, the classical algorithms remain central. Modern developments:

• Robustness: Exact geometric computation and robust predicates
• Streaming geometry: Processing massive geometric data in limited memory
• Distributed geometry: Computing geometric structures across multiple machines
• Learned geometry: ML methods for geometric recognition combined with classical algorithms

Cross-disciplinary applications expanding: Geometric thinking appears in unexpected places:

• Network analysis (embedding graphs in space)
• Machine learning (nearest neighbors, clustering)
• Bioinformatics (protein structure)
• Economics (spatial equilibrium models)

Understanding geometric algorithms opens doors to all these areas.

Ready for students? ✓ Yes - strong motivation from graphics/robotics/GIS, clear problem progression, multiple implementation projects, connects theory to visual/spatial intuition.