Randomized Algorithms in Computational Geometry

Randomized Algorithms in Computational Geometry

Randomness is especially useful in geometry because a poor deterministic order can make a simple incremental algorithm repeatedly rebuild its largest structure. Shuffle the same objects first, and the expensive cases become rare in expectation. The resulting algorithms are often short, local, and fast—yet their guarantees require more care than the slogan “random input is easy.”

The model is usually a fixed, possibly adversarial set of geometric objects followed by a uniformly random permutation. The coordinates are not random. Only the processing order is. This distinction lets randomized algorithms handle clustered, aligned, or otherwise unpleasant inputs without pretending those inputs came from a friendly distribution.

Las Vegas and Monte Carlo guarantees

A Las Vegas algorithm always returns a correct answer; randomness affects only running time or space. Randomized incremental trapezoidal maps and Delaunay triangulations are normally designed this way. If an insertion order is unlucky, the construction takes longer, but it must not return a wrong subdivision.

A Monte Carlo algorithm has a fixed or predictably bounded cost but may return an incorrect answer with small probability. Repetition can reduce that probability—for example, independent trials with failure probability at most $p$ fail together with probability at most $p^r$. Monte Carlo methods appear in sampling, verification, and approximate geometry, but a claimed error probability is meaningful only when its assumptions and failure event are stated.

A third pattern combines them: compute a candidate quickly with a randomized method, verify it deterministically, and restart on failure. Verification converts a one-sided Monte Carlo construction into Las Vegas behavior when the verifier is sound.

The random-permutation model

Let $S=\{x_1,\ldots,x_n\}$ be fixed. Choose one of its $n!$ permutations uniformly and insert objects in that order. Equivalently, assign each object an independent random priority and process increasing priorities. Conditioned on the first $i$ objects, each of those objects is equally likely to have been inserted last.

That symmetry powers backward analysis. Instead of asking how much damage the next random object causes—a question that may depend on complicated history—look at the completed structure on $i$ objects and remove its uniformly random last object. If only a small number of objects define the feature being charged, removal changes that feature with small probability.

Suppose every feature in a structure on $i$ objects is defined by at most $b$ objects, and there are $O(i)$ features. A fixed feature disappears under random deletion with probability at most $b/i$. Summed over all features, the expected number destroyed is $O(1)$. Reversing time says the expected structural change caused by insertion $i$ is $O(1)$. If locating the conflict costs $O(\log i)$ expected time, the total often becomes $O(n\log n)$.

The proof must identify exactly what is charged. “Constant expected change” does not automatically imply constant insertion time: finding the affected region, traversing a cavity, and updating a search structure may add costs.

Randomized incremental construction

Randomized incremental construction (RIC) follows a reusable plan:

1. Shuffle the objects uniformly.
2. Maintain a correct structure for the inserted prefix.
3. Locate features conflicting with the next object.
4. Delete or split those features and create replacements.
5. Update an auxiliary structure so later conflicts can be found efficiently.

A conflict graph explicitly links uninserted objects to current features they would invalidate. When an insertion destroys features, only their incident candidates need testing against the replacements. This can make analysis clean, but storing all current conflicts may be expensive.

A history DAG keeps obsolete features as routing nodes. A query begins at the initial structure and follows children whose regions may contain the query until reaching a live feature. Multiple parents share replacement nodes, hence a DAG rather than a tree. History preserves enough information to locate future insertions without maintaining every future conflict explicitly.

The choice is application-specific. A trapezoidal map naturally retains a search DAG of point and segment decisions. Bowyer–Watson Delaunay construction often locates one conflicting triangle, then floods across adjacent triangles to discover the cavity. Some analyses use an abstract conflict graph even when the implementation stores adjacency plus a point-location aid.

Three canonical examples

Trapezoidal maps. Insert noncrossing segments in random order. A segment walks through the trapezoids it intersects, splits them, and updates a history DAG. Backward analysis asks how many trapezoid boundaries can be attributable to the last segment. The construction has expected $O(n\log n)$ time and $O(n)$ space under the standard general-position model; query paths are expected $O(\log n)$. Tail control matters because expectation over an entire DAG is not itself a per-instance depth guarantee. Part 15 develops the structure and its degeneracy rules.

Delaunay triangulations. Insert points into a containing supertriangle. Locate triangles whose circumcircles contain the new point, remove that connected cavity, and join the new point to its boundary. Since planar triangulations have linear complexity and a triangle has three defining sites, backward analysis yields constant expected combinatorial change per insertion; point location leads to expected $O(n\log n)$ total time. Part 17 covers conflict discovery, flips, and cocircular inputs.

Smallest enclosing discs. Process points in random order. If the new point lies inside the current disc, nothing changes. Otherwise it lies on the boundary of the new optimum, reducing the remaining problem to one with that point fixed; at most three points define a planar minimum disc. Nested backward analysis gives expected linear time despite the algorithm’s quadratic- or cubic-looking loops.

def minimum_disc(points, boundary=()):
    """Las Vegas: exact result; random order controls expected time."""
    if not points or len(boundary) == 3:
        return disc_defined_by(boundary)

    p = points.pop()                 # points was shuffled once
    disc = minimum_disc(points, boundary)
    if robustly_inside_or_on(p, disc):
        points.append(p)
        return disc

    disc = minimum_disc(points, boundary + (p,))
    points.append(p)
    return disc

def solve(points, seed):
    rng = Random(seed)
    ordered = list(deduplicate(points))
    rng.shuffle(ordered)
    return minimum_disc(ordered)

The code shows the mathematical recursion, not a complete numeric implementation. disc_defined_by must handle zero, one, two, or three boundary points, including collinear triples; robustly_inside_or_on must use a consistent closed-disc predicate.

Expected time is not a tail bound

An expectation $E[T]=O(n\log n)$ permits rare, very slow executions. Markov’s inequality gives only

$$\Pr[T\ge cE[T]]\le 1/c,$$

which is useful but weak. Stronger high-probability claims—typically failure at most $n^{-c}$ for a chosen constant $c$—need additional arguments such as bounded differences, martingales, independent sampling rounds, or structure-specific restart tests. One cannot simply replace “expected” by “with high probability.”

In practice, make rare bad runs observable. Track history-DAG depth, conflict-region size, and cumulative rebuild work. If a verified threshold is exceeded, reshuffle with a new seed and rebuild. If each attempt exceeds the threshold with probability at most $q<1$, independent restarts make $r$ consecutive overruns at most $q^r$. The threshold and independence assumptions belong in the engineering contract.

Adversaries, reproducibility, and testing

A shuffle protects against an adversarial input order only if priorities are unpredictable to the adversary. A fixed public seed is excellent for reproduction but not for security against an adaptive party that can choose coordinates after seeing priorities. Decide which model applies: offline fixed input, oblivious adversary, or adaptive adversary. Randomized geometry is not automatically adversary-resistant.

Reproducibility is still essential. Accept or record a seed, the PRNG algorithm/version, input normalization rules, and stable object identifiers. Do not seed from wall-clock time inside the constructor. A failing permutation should be replayable byte for byte. Test several layers:

• deterministic edge suites: duplicates, collinearity, cocircularity, shared endpoints, vertical segments, and huge coordinate ranges;
• many recorded seeds on the same hostile point sets;
• differential checks against a slow exact algorithm on small instances;
• permutation-invariance checks on canonicalized output;
• structural audits after every insertion in debug builds;
• budget tests that report tail percentiles rather than only the mean.

Random order never repairs an inconsistent predicate. Orientation, in-circle, containment, and intersection decisions define topology. Floating-point roundoff can make a history DAG route into no live feature or make a Delaunay cavity nonconnected. Use exact integer/rational signs where feasible, filtered predicates with exact fallback otherwise, and a symbolic perturbation or deterministic tie-break policy for true zeros. Keep construction predicates and query predicates consistent.

A proof-and-implementation checklist

Before trusting a randomized geometric algorithm, state five things precisely: the fixed input and source of randomness; the invariant true after every insertion; the defining objects used by backward analysis; the cost of locating and repairing conflicts; and whether the final claim is expectation, high probability, or bounded error. Then state the degeneracy policy separately.

This discipline explains why randomized construction is so effective without treating randomness as magic. Local geometric complexity supplies small defining sets; a random permutation makes each object equally likely to be last; backward analysis turns that symmetry into expected bounds; and robust predicates preserve the combinatorial structure on which the proof depends.