17.24 Performance Optimization

Problem

Many geometric algorithms are already asymptotically optimal.

For example:

convex hull           O(n log n)
closest pair          O(n log n)
rectangle union       O(n log n)
KD-tree query         O(log n) average

Yet practical implementations can still be slow.

The reason is that geometric software often spends most of its time in:

predicate evaluation
memory allocation
sorting
cache misses
candidate generation
repeated computations

Performance optimization in geometry is therefore less about inventing new algorithms and more about reducing unnecessary work.

Solution

Optimize geometry systems in layers.

Start with:

correctness

then:

algorithmic complexity

then:

data structures

and finally:

micro-optimizations

This order matters.

A correct O(n log n) algorithm almost always beats a highly optimized O(n²) algorithm on large datasets.

Measure Before Optimizing

Always profile first.

A geometry pipeline might appear expensive in one area while spending most of its time elsewhere.

Example:

spatial query
    ↓
candidate generation
    ↓
polygon intersection

You might expect polygon intersection to dominate.

Profiling may reveal:

70% bounding-box creation
20% polygon intersection
10% everything else

Without measurement, optimization becomes guesswork.

Cache Derived Geometry

Many geometric quantities never change.

Examples:

bounding boxes
polygon area
centroids
sorted coordinate lists
compressed coordinate maps

Bad pattern:

def polygon_intersects(a, b):
    box_a = bounding_box(a)
    box_b = bounding_box(b)

    ...

If this function runs thousands of times, the same boxes are recomputed repeatedly.

Better:

polygon.bounding_box

computed once.

Example:

class Polygon:
    def __init__(self, vertices):
        self.vertices = vertices
        self.bounding_box = compute_box(vertices)

The cost becomes:

one computation
many lookups

Reduce Expensive Predicates

Geometric predicates often dominate runtime.

Examples:

segment intersection
point-in-polygon
distance computation
orientation tests

A common optimization:

cheap filter
    ↓
expensive predicate

For segment intersection:

if not boxes_intersect(box1, box2):
    return False

return exact_segment_intersection(...)

Bounding-box rejection can eliminate most comparisons.

Prefer Squared Distances

Distance comparisons appear everywhere.

Bad:

from math import sqrt

distance = sqrt(dx * dx + dy * dy)

Better:

distance2 = dx * dx + dy * dy

Compare squared values:

if distance2 < best_distance2:
    ...

Benefits:

fewer floating-point operations
no square roots
better numerical behavior

This optimization is standard in:

nearest neighbor
collision detection
clustering
closest pair

Avoid Angles When Possible

Angle computation is expensive.

atan2(y, x)

requires trigonometric functions.

Many algorithms only need ordering.

Use:

cross products
dot products
orientation tests

instead.

Example:

orientation(a, b, c)

often replaces angle comparison entirely.

Benefits:

faster
simpler
more numerically stable

Sort Once

Sorting frequently dominates runtime.

Bad pattern:

for query in queries:
    points.sort(...)

Better:

points.sort(...)

once.

Reuse the sorted order whenever possible.

Many geometric algorithms gain efficiency from maintaining sorted structures:

sweep lines
closest pair
KD-tree construction
convex hull

Repeated sorting often hides inside otherwise efficient code.

Coordinate Compression

Large coordinate ranges frequently appear in:

interval geometry
rectangle union
segment trees
range queries

Example:

1000000000
5000000000
9000000000

Only ordering matters.

Compress:

0
1
2

Benefits:

smaller memory footprint
better cache locality
faster indexing

Coordinate compression is one of the most effective optimizations for sweep-line algorithms.

Improve Memory Locality

Modern processors often spend more time waiting for memory than performing arithmetic.

Bad layout:

linked structures
many small allocations
pointer-heavy trees

Better layout:

contiguous arrays
compact structures
structure-of-arrays layouts

Example:

points_x = [...]
points_y = [...]

instead of:

points = [
    Point(...),
    Point(...),
]

In performance-critical systems, memory layout can matter more than arithmetic cost.

Batch Operations

Suppose many points need the same transformation.

Bad:

for point in points:
    transform(point)

with repeated setup work.

Better:

precompute transform
apply to all points

Example:

cos_theta = cos(theta)
sin_theta = sin(theta)

for point in points:
    ...

instead of recomputing trigonometric functions for every point.

Exploit Convexity

Convex geometry is often dramatically faster.

Examples:

Problem	General	Convex
Containment	O(n)	O(log n) possible
Diameter	Harder	Rotating calipers
Intersection	More complex	Simpler
Optimization	Harder	Easier

Pipeline:

general geometry
    ↓
convex decomposition
    ↓
convex algorithms

Many collision systems use exactly this strategy.

Use Spatial Indexes

The fastest geometric predicate is the one you never evaluate.

Suppose:

1,000,000 objects

Naive collision testing:

O(n²)

Spatial partitioning:

grid
KD-tree
quadtree
R-tree
BVH

reduces comparisons dramatically.

Pattern:

spatial index
    ↓
candidate objects
    ↓
exact geometry

This often produces orders-of-magnitude speedups.

Incremental Updates

Rebuilding structures repeatedly is expensive.

Bad:

for frame in simulation:
    rebuild_kdtree()

Better:

update affected regions only

Examples:

dynamic BVH
incremental Delaunay
mutable spatial hash

Incremental maintenance often converts:

O(n log n)

per update into much smaller costs.

Parallelism

Many geometric operations parallelize naturally.

Examples:

bounding-box generation
distance calculations
point transformations
polygon area calculations

Example:

partition objects
process partitions independently
merge results

Embarrassingly parallel workloads frequently appear in:

GIS
point clouds
rendering
simulation

However, sweep-line algorithms and certain tree structures may require more careful synchronization.

Early Termination

Many algorithms can stop once the answer is known.

Example:

for segment in segments:
    if segments_intersect(query, segment):
        return True

No need to inspect the remaining segments.

Likewise:

if distance2 == 0:
    return point

during nearest-neighbor search.

Early exits are simple and often highly effective.

Vectorization

For large numeric datasets:

point clouds
GIS coordinates
mesh vertices
simulation particles

batch arithmetic can outperform object-oriented loops.

Example:

apply translation
apply scaling
compute distances

on arrays rather than individual objects.

Modern numeric libraries are heavily optimized for this style.

Avoid Premature Optimization

A common failure pattern:

micro-optimization
before
algorithm selection

Example:

optimize segment intersection

while still performing:

O(n²)

comparisons.

The better improvement:

spatial index

may reduce comparisons by several orders of magnitude.

Always optimize at the highest-impact level first.

Complexity vs Constants

Two implementations may have the same complexity:

O(n log n)

yet differ substantially in practice.

Factors include:

memory locality
allocation count
cache behavior
branch prediction
data distribution

This is why profiling remains essential.

Theoretical complexity predicts scaling.

Profiling reveals actual cost.

Performance Checklist

Before optimizing a geometry system, ask:

Can a better algorithm be used?
Can a spatial index remove work?
Can bounding boxes reject candidates?
Can values be cached?
Can sorting be avoided?
Can squared distances replace square roots?
Can convexity simplify the problem?
Can updates be incremental?
Can computations be batched?

These questions often produce larger gains than low-level tuning.

Common Pitfalls

Optimizing Before Measuring

Profile first.

Recomputing Derived Data

Cache stable quantities.

Ignoring Candidate Filtering

Bounding boxes and spatial indexes are often the biggest wins.

Overusing Trigonometry

Cross products and dot products are usually cheaper.

Chasing Microseconds in Quadratic Algorithms

Fix algorithmic complexity before micro-optimizing.

Discussion

Performance optimization in computational geometry is largely about reducing the number of geometric predicates that must be evaluated. Spatial indexes reduce search space. Bounding boxes eliminate impossible cases. Convexity simplifies structure. Coordinate compression improves locality. Incremental maintenance avoids rebuilding.

The most successful geometry systems combine these techniques. They use efficient algorithms, aggressive filtering, careful data representation, and robust predicates. The result is software that remains both correct and fast as datasets grow from hundreds of objects to millions.