Choosing, Testing, and Engineering Geometric Algorithms

Choosing, Testing, and Engineering Geometric Algorithms

Part 22 turned free space into a visibility graph and reduced Euclidean route planning to graph search. That reduction was mathematically clean; a dependable implementation is less tidy. Is touching an obstacle allowed? Can coordinates be rounded? Will obstacles change between queries? Is one route needed, or ten million? The right algorithm is determined as much by these contracts as by asymptotic notation.

This final core part develops a practical discipline for choosing, testing, and measuring geometric software. The central lesson is that an algorithm is not just a theorem plus code. It is a package of representations, predicates, degeneracy rules, performance assumptions, and evidence.

Start with a geometric data contract

A useful contract states the coordinate domain, valid object shapes, topology conventions, output guarantees, and resource targets. For a route planner, for example, specify whether polygons are simple, whether holes have a fixed orientation, whether touching a boundary counts as collision, and whether the returned path must be exactly shortest or merely feasible within a tolerance.

Normalize input once at the boundary. Assign stable identifiers; remove consecutive duplicate vertices; validate rings; standardize orientation; and reject NaNs, infinities, malformed polygons, or unsupported coordinate magnitudes. Do not let every downstream predicate invent its own cleanup policy. Preserve original input separately when auditability matters.

Distinguish three kinds of equality:

• numeric equality, such as two stored coordinates having identical bits;
• geometric equality, such as two constructed points representing the same location; and
• combinatorial identity, such as two half-edges belonging to the same subdivision feature.

Conflating them causes famous failures: a point rounded differently along two construction paths becomes two vertices, or a tolerance merges distinct narrow corridors. Topological structures should refer to stable feature identities, not rediscover adjacency from approximate coordinates.

Arithmetic is an architectural decision

Most geometric algorithms branch on signs: orientation, in-circle, sidedness, or segment intersection. If a computed sign is wrong, the program may not merely return a slightly inaccurate coordinate; it may build an impossible topology.

Exact arithmetic evaluates the required signs without roundoff, using bounded integers where overflow is proved impossible, wider integers, rationals, expansions, or algebraic-number machinery. It gives strong guarantees but can increase constant factors and representation complexity. Exact predicates do not automatically imply exact constructions: the intersection of rational lines may require rational coordinates even when inputs are integers.

Filtered predicates first evaluate with fast floating point and an error bound. If the magnitude is safely outside the uncertainty interval, accept the sign; otherwise fall back to exact evaluation. Well-designed filters often approach floating-point speed on ordinary data while preserving exact combinatorial decisions.

Approximate computation is appropriate when the contract permits bounded geometric error and topology is not inferred from unstable signs. Examples include display-only simplification, approximate nearest neighbors, and sampling-based estimates. An epsilon is not a proof of correctness. A fixed tolerance changes meaning under scaling, and different predicates can disagree inside overlapping tolerance bands.

A robust kernel separates predicates from constructions, centralizes the number policy, and defines exact behavior for true zeros. Symbolic perturbation or deterministic tie-breaking can resolve degeneracies, but its ordering must be used consistently across the entire pipeline.

Match the algorithm to the workload

The same geometric question has different best solutions under different workloads. An offline algorithm sees the entire batch and may sort, sweep, compress coordinates, or globally optimize. An online algorithm must answer as requests arrive. A static structure assumes the data set stays fixed; a dynamic one supports insertion or deletion, often with higher constants and weaker bounds.

Preprocessing is worthwhile only when enough queries amortize it. If construction costs $P(n)$, each indexed query costs $Q(n)$, and a direct query costs $D(n)$, an index becomes attractive around

\[ m \gt \frac{P(n)}{D(n)-Q(n)}, \]

provided memory, update costs, and latency limits also fit. Measure the actual crossover; constants and cache behavior can dominate.

Output-sensitive algorithms express time in both input size $n$ and answer size $k$, as in reporting intersections in $O((n+k)\log n)$. They shine when outputs are usually small, but cannot avoid spending $\Omega(k)$ to emit a large answer. Likewise, expected bounds from randomized algorithms may be excellent against unknown or adversarial input order, while deterministic algorithms are preferable when repeatable latency or certification matters. Randomized need not mean irreproducible: record the seed, generator, and input order.

Preserve topology across stages

Robust geometry is a pipeline property. If segment intersection reports a crossing that subdivision assembly later snaps away, both routines may look locally reasonable while the global result is invalid. Define one boundary policy—open, closed, or half-open—and one degeneracy vocabulary for shared endpoints, overlaps, tangencies, collinearity, and zero-area features.

After each topology-changing stage, check structural invariants. A DCEL can verify twin symmetry, closed face cycles, and consistent next/previous links. A triangulation can check positive face orientation and edge incidence. A route planner can certify that every path segment lies in closed free space under its stated contact policy. Assertions close to the mutation locate defects far better than a final “no path” result.

Test relationships, not only examples

Hand-picked examples are necessary and insufficient. Build an adversarial suite containing empty sets, one object, duplicates, shared endpoints, vertical lines, collinear and cocircular sets, tiny separations, huge and mixed coordinate scales, repeated vertices, narrow corridors, and dense outputs. Include configurations just on both sides of each decision boundary.

Then add generative methods:

• Property tests check invariants: hull vertices come from the input, reported intersections lie on both segments, or a path avoids obstacle interiors.
• Differential tests compare a fast implementation with a slower, simpler, preferably exact oracle on small random cases.
• Metamorphic tests transform the input when the answer relationship is known. Translation should translate a hull; positive scaling should preserve incidence; permuting input should preserve canonical output; swapping segment endpoints should not alter intersection geometry.
• Round-trip tests serialize and reload structures, or move from polygons to a subdivision and back, then compare canonical geometry and topology.

Canonicalization matters. Sort unordered outputs, normalize ring rotations and orientations, and compare exact feature identities where available. A raw list-order mismatch is not a geometric failure; a hidden missing edge is.

from dataclasses import dataclass
import random

@dataclass(frozen=True)
class Failure:
    seed: int
    case: object
    fast: object
    oracle: object

def canonical(result):
    return tuple(sorted(result))       # replace with domain normalization

def check_case(case, fast, oracle):
    got = canonical(fast(case))
    want = canonical(oracle(case))
    assert got == want

    dx, dy = 17, -31
    moved = translate_case(case, dx, dy)
    moved_got = canonical(fast(moved))
    assert moved_got == canonical(translate_result(got, dx, dy))

def campaign(seed, trials, generator, fast, oracle):
    rng = random.Random(seed)
    for trial in range(trials):
        case = generator(rng, size=1 + trial % 40)
        try:
            check_case(case, fast, oracle)
        except AssertionError:
            save_failure(seed=seed, trial=trial, case=case)
            raise

When a generator finds a failure, shrink it while retaining the failure: delete objects, reduce coordinate magnitudes, and simplify rings. Save the minimal case with software version, numeric mode, platform, seed, and full contract. It becomes a permanent regression test.

Visualize decisions, benchmark distributions

Visualization is an instrument, not proof. Render predicate signs, event order, active sweep status, constructed vertices, rejected visibility edges, and exact failure coordinates. Layer identifiers and tolerances onto the picture. The most valuable view often shows the algorithm’s internal decisions beside the geometric result.

Benchmark end-to-end time and meaningful phases: normalization, preprocessing, predicates and fallbacks, topology construction, queries, validation, and serialization. Report memory, output size, fallback count, and update count. Use warmups where appropriate, pin versions and hardware details, isolate I/O, and publish the data generator. Report median and tail percentiles rather than one best run. Sweep input size and structure—uniform, clustered, grid-like, nearly degenerate, and adversarial—not just (n).

Reproducibility requires stable seeds, deterministic tie-breaks, recorded configuration, and versioned benchmark corpora. If parallel scheduling changes output order, canonicalize it; if it changes topology, investigate the race or underspecified tie.

A decision workflow

Use this sequence before committing to an implementation:

1. Write the contract. Define domains, degeneracies, boundary semantics, accuracy, and failure behavior.
2. Characterize the workload. Estimate (n), output size, query count, updates, latency, memory, and adversarial exposure.
3. Choose the numeric kernel. Prefer exact or filtered decisions whenever topology depends on signs.
4. Shortlist algorithms. Compare preprocessing, query, update, output-sensitive, deterministic, and expected costs—including constants.
5. Prototype the simplest viable candidate. Instrument phases, predicates, and invariants from the beginning.
6. Attack it. Run adversarial, property, differential, and metamorphic tests; save and shrink every failure.
7. Measure the crossover. Benchmark representative distributions and tails, then document when another method should replace this one.
8. Ship evidence with the code. Keep the contract, oracle tests, failure corpus, benchmark recipe, and reproducibility metadata versioned together.

This workflow closes the conceptual arc of the series. Predicates supply trusted decisions; subdivisions preserve topology; decompositions and search structures organize space; and algorithms exploit those structures. Engineering binds them into one coherent system.

The capstone now puts that discipline under load. A polygonal robot route planner must expand obstacles by a reflected robot, construct or query free space, build visibility relationships, and search for a route. Its success will depend not only on Minkowski sums and Dijkstra’s algorithm, but also on an explicit contact policy, consistent predicates, structural validation, adversarial narrow passages, and replayable benchmarks. That is the final step from knowing geometric algorithms to trusting a geometric product.