17.21 Geometry Design Patterns
After studying individual geometric algorithms, it is tempting to view them as unrelated techniques.
17.21 Geometry Design Patterns
Problem
After studying individual geometric algorithms, it is tempting to view them as unrelated techniques.
You may have encountered:
convex hulls
sweep lines
Voronoi diagrams
Delaunay triangulations
spatial indexes
segment trees
rotating calipers
polygon clipping
At first glance, these algorithms appear completely different.
In practice, however, most computational geometry systems are built from a surprisingly small collection of recurring design patterns.
Understanding these patterns is often more valuable than memorizing individual algorithms.
Solution
Learn to recognize the structural ideas that repeatedly appear in geometric problem solving.
The most important patterns include:
geometric predicates
divide and conquer
sweep line
incremental construction
duality
spatial partitioning
hierarchical decomposition
filter and refine
local optimization
Once these patterns become familiar, new geometric algorithms become much easier to understand.
Pattern 1: Geometric Predicates
Nearly every algorithm in this chapter relies on a few basic questions:
left or right?
inside or outside?
intersect or not?
closer or farther?
Examples:
orientation
point-in-polygon
segment intersection
in-circle test
The algorithm itself is often little more than a sophisticated arrangement of predicates.
For example:
convex hull
depends primarily on:
orientation(a, b, c)
Likewise:
half-plane intersection
depends largely on:
orientation
line intersection
A useful rule:
good predicates
↓
good geometry
Pattern 2: Divide and Conquer
Several major algorithms use recursive decomposition.
Examples:
closest pair
Delaunay triangulation
Voronoi construction
range searching
General structure:
divide
↓
solve recursively
↓
merge
Closest pair:
split points
solve left
solve right
check strip
The challenge is usually not the recursion.
The challenge is designing an efficient merge step.
Pattern 3: Sweep Line
Sweep-line algorithms transform geometry into event processing.
Examples:
segment intersection
rectangle union
maximum overlap
event scheduling
General pattern:
sort events
maintain active set
process changes
Visual idea:
|
|
--------|-------->
|
|
The moving line reduces a two-dimensional problem into a sequence of one-dimensional updates.
Whenever a problem changes only at discrete locations, a sweep-line solution is worth considering.
Pattern 4: Incremental Construction
Many geometric structures can be built one object at a time.
Examples:
Delaunay triangulation
Voronoi diagrams
convex hulls
spatial indexes
General structure:
start simple
insert one object
repair local violations
repeat
Delaunay insertion:
insert point
find affected triangles
repair
Convex hull insertion:
insert point
remove invalid vertices
Incremental algorithms are often conceptually simple and easy to implement.
Pattern 5: Local Repair
Some algorithms achieve global correctness through local fixes.
Examples:
edge flipping
rotating calipers
incremental hull maintenance
Delaunay triangulation is a classic example.
A globally correct triangulation emerges from repeatedly repairing illegal edges.
illegal edge
↓
flip
↓
legal edge
Repeated local improvement eventually produces a globally valid structure.
Pattern 6: Spatial Partitioning
Large geometric datasets are often divided into regions.
Examples:
KD-tree
quadtree
R-tree
Voronoi diagram
uniform grid
General structure:
space
↓
smaller regions
↓
local search
Instead of searching:
everything
search only:
relevant regions
This is one of the most important performance techniques in practical geometry.
Pattern 7: Hierarchical Decomposition
Many structures organize geometry into levels.
Examples:
quadtrees
BVHs
R-trees
segment trees
Visual idea:
root
├─ child
│ ├─ child
│ └─ child
└─ child
Queries descend only into relevant branches.
Hierarchy converts:
O(n)
searches into:
O(log n)
or near-logarithmic searches.
Pattern 8: Duality
Sometimes a difficult geometric problem becomes easier after transforming it into another space.
The most famous example:
Voronoi diagram
⇄
Delaunay triangulation
A Voronoi edge corresponds to a Delaunay edge.
A Delaunay triangle corresponds to a Voronoi vertex.
Duality often reveals structure that is difficult to see directly.
Pattern 9: Convexification
Many difficult geometric problems become simpler after reducing them to convex geometry.
Examples:
convex hull
convex decomposition
support functions
rotating calipers
Pipeline:
general geometry
↓
convex representation
↓
simpler algorithm
Convex objects have powerful properties:
unique supporting lines
ordered boundaries
simple containment tests
Many algorithms exploit these properties.
Pattern 10: Filter and Refine
Practical geometry systems rarely run expensive algorithms immediately.
Instead:
cheap filter
↓
expensive verification
Example:
bounding box
↓
polygon intersection
Or:
R-tree
↓
exact geometry
Or:
spatial hash
↓
collision test
This pattern appears everywhere because most objects are irrelevant.
Pattern 11: Coordinate Transformation
Some problems become easier after changing coordinates.
Examples:
translation
rotation
projection
compression
normalization
Instead of solving:
hard problem
directly, transform it into:
easier problem
Coordinate compression is a common example.
Large coordinates:
1000000
5000000
9000000
become:
0
1
2
while preserving ordering.
Pattern 12: Exact Predicate, Approximate Construction
This pattern appears repeatedly in robust geometry.
Use:
exact arithmetic
for decisions.
Use:
floating-point arithmetic
for coordinates and measurements.
Example:
orientation
must be reliable.
intersection point
may tolerate small approximation errors.
This approach balances correctness and performance.
Pattern 13: Event-Driven Geometry
Some geometric systems evolve over time.
Examples:
sweep-line algorithms
kinetic data structures
physics simulations
motion planning
State changes only when significant events occur.
event
↓
update state
↓
continue
This often eliminates unnecessary work.
Pattern 14: Amortized Movement
Several algorithms appear quadratic but are actually linear because pointers move monotonically.
Examples:
rotating calipers
two-pointer interval scans
merge operations
Key idea:
pointer never moves backward
Therefore:
total movement ≤ O(n)
This pattern appears frequently in geometric optimization.
Pattern 15: Geometric Reduction
Many geometry problems reduce to another geometry problem.
Examples:
rectangle overlap
↓
interval overlap
polygon area
↓
cross products
nearest neighbor
↓
point location
collision detection
↓
bounding-box tests
A useful habit is asking:
what simpler problem does this become?
before designing a new algorithm.
Recognizing Patterns in New Problems
Suppose a problem asks:
find all overlapping rectangles
Possible pattern recognition:
events
active intervals
suggests:
sweep line
Suppose a problem asks:
nearest point among millions
Possible pattern recognition:
spatial partitioning
hierarchy
suggests:
KD-tree
quadtree
Suppose a problem asks:
optimize over a convex region
Possible pattern recognition:
convex geometry
supporting lines
suggests:
half-plane intersection
rotating calipers
Pattern recognition is often more important than remembering a specific algorithm.
Common Pitfalls
Memorizing Algorithms Without Structure
Patterns transfer. Individual implementations do not.
Ignoring Convexity
Many hard problems become easier after convex reduction.
Using Exact Geometry Too Late
Robust predicates should be part of the design, not an afterthought.
Skipping Filtering Stages
Exact geometry is often expensive.
Reinventing Existing Patterns
Many new problems are variations of known geometric templates.
Discussion
Computational geometry contains hundreds of algorithms, but far fewer design patterns. Sweep lines, divide and conquer, spatial partitioning, convexification, filtering, hierarchical decomposition, and robust predicates appear repeatedly across the field. Once you begin recognizing these recurring ideas, new algorithms become easier to derive, understand, and implement.
This chapter concludes with a final summary that ties together the major themes of computational geometry and highlights the techniques that appear most often in real-world geometric software.