Randomized Incremental Construction and Backward Analysis

Many geometric structures are easiest to describe incrementally: start with a small piece, add one input element at a time, and repair the structure after each addition. The repair can be expensive, and in the worst order it is expensive at every step, which makes the total quadratic or worse. Inserting the elements in uniformly random order changes the total cost from a worst-case quantity to an expected one, and the expected value is often linear. The analysis technique that establishes this is unusual: it reasons about the process in reverse.

The conflict graph and what insertion costs

The canonical example is the Delaunay triangulation built by incremental insertion. Points are added one at a time; each new point falls inside exactly one existing triangle, which is split into three, and the edges of the resulting polygon are then flipped while the empty-circumcircle property is violated. The number of flips is bounded by the degree of the new vertex in the final triangulation, and the total work is the sum over insertions of the cost of locating the containing triangle plus the number of flips.

Locating the triangle naively costs a scan over all current triangles, which is Θ(i) at step i and Θ(n^2) overall. A conflict graph removes the scan: each uninserted point is recorded against the triangles whose circumcircle contains it, so the containing triangle for the next point is found by following the conflicts from the previously split triangle. Maintaining the conflict graph costs work proportional to the number of conflict pairs that are created and destroyed.

The total expected cost is then dominated by the number of conflict pairs. A pair of (triangle, point) exists when the triangle’s circumcircle contains the point, and a point that lies inside a triangle’s circumcircle is in conflict with it. The number of such pairs at any moment is the quantity to bound, and it is not obviously small: a large triangle early in the process can conflict with many points.

Backward analysis reverses the insertion order

The trick is to analyse the structure as it was just before the last insertion rather than just after it. Fix the set of i points that have been inserted at some stage, and ask what the structure looked like before the i-th insertion. In a random insertion order, the i-th point is a uniformly random element of those i points, so the structure on the remaining i-1 points is the structure that would have been built from that subset. The analysis can then be phrased in terms of the final structure on the i points.

The specific consequence for the triangulation: the number of triangles created when the i-th point is inserted equals the number of triangles in the triangulation of the first i points that are incident to that point. Since the inserted point is uniform over the i points, the expected number of incident triangles is the average degree of a vertex in the triangulation of those i points. For a planar triangulation on i vertices the average degree is below 6, by the Euler relation: 3f = 2e and v - e + f = 2 give e < 3v, so the average degree 2e/v is below 6.

That single number, an average degree below 6 in a planar graph, is what makes the expected cost per insertion constant. Summed over n insertions, the expected total number of created triangles is below 6n, so the expected total work is Θ(n) once the point location is handled.

The same reversal gives the bound on the conflict graph. The expected number of conflicts at step i is bounded by summing, over the triangles present at that step, the probability that a uniformly random remaining point lies in the triangle’s circumcircle. That probability is the triangle’s “weight”: the number of input points inside its circumcircle divided by the number of remaining points. It the sum of the weights over the triangles of the current triangulation is bounded by a constant per point by a packing argument.

Why the argument needs a random order, not a random input

The bound uses the uniformity of the inserted element over the current point set. It does not assume anything about where the points are. A set of points arranged adversarially, with all of them on a circle or in a thin cluster, produces the same expected bound as a uniform random set, because the argument averages over the insertion order and not over the positions.

This is the practical value of the technique: geometric inputs are rarely random, and adversarial configurations are common in the form of degenerate data. Randomizing the order makes the analysis independent of the geometry, at the cost of destroying any spatial locality that a sorted insertion order would have provided. For data that arrives sorted along an axis, inserting in that order gives excellent cache behaviour and terrible structure; inserting in random order gives the reverse.

The order must be a uniformly random permutation, which means the draws come from the primitive in Unbiased Random Integers from a Finite Random Source. A shuffle that is only approximately uniform is usually fine for the constant, but a shuffle that leaves the input order substantially intact, such as swapping each element with a neighbour, does not give the bound.

import random

def random_order(points):
    order = list(range(len(points)))
    for i in range(len(order) - 1, 0, -1):
        j = random.randrange(i + 1)
        order[i], order[j] = order[j], order[i]
    return order

The permutation itself is the subject of Uniform Random Permutations, and the inside-out variant is what allows the order to be generated for a stream of points whose count is unknown.

The general shape of the technique

Randomized incremental construction applies whenever three conditions hold. The structure for a set S is determined by S and can be updated locally when one element is added. The cost of the update is bounded by the number of structural features incident to the new element in the structure on the current set. And the final structure on a random subset is itself a random structure whose feature count can be bounded by a combinatorial argument.

The third condition is where the geometry enters. For the Delaunay triangulation it is the planar average degree. For a trapezoidal map of line segments it is the fact that the map has linear complexity and each insertion adds a bounded number of trapezoids. For the smallest enclosing circle, the analogous statement is that the circle is determined by at most three points, so the probability that the i-th point changes the answer is at most 3/i, and the expected total cost is Θ(n) by the harmonic sum.

That last example shows the technique in its purest form. The algorithm processes points in random order, maintaining the smallest enclosing circle of the points seen so far. When a new point lies outside the current circle, the circle must be recomputed with that point on its boundary; the recomputation recurses on the points seen so far, and each recursive level is triggered only when a new point lies outside. The probability that the i-th point triggers a recomputation at the top level is at most 3/i, because the final circle is determined by three points and each is equally likely to be the last of the three in the random order. The recursion has the same structure at each level, giving a total expected cost of Θ(n) for a constant number of levels.

Degeneracies and the cost of exactness

Geometric algorithms are sensitive to degeneracies: collinear points, cocircular points, duplicate points. A set of points on a circle has a Delaunay triangulation that is not unique, and an incremental algorithm that assumes a unique containing triangle will fail on the first point that lands on an existing edge.

The standard treatment is symbolic perturbation: a consistent infinitesimal displacement of the input that removes all degeneracies without changing the combinatorial answer for non-degenerate cases. The perturbation must be applied consistently in every geometric predicate, which means the orientation and incircle tests must be evaluated in the perturbed arithmetic rather than the original. Doing this correctly is the source of much of the complexity in real implementations, and it interacts with the randomization only through the analysis: the perturbation is fixed, so the expected bound still holds.

The other cost is exact arithmetic. Predicates evaluated in floating point can give the wrong sign for nearly degenerate configurations, and a single wrong sign can make the incremental structure inconsistent. Exact predicates using adaptive precision are the usual remedy; they cost more per call but preserve the invariants the analysis assumes. The randomized bound is a statement about the number of structural changes, and it survives exact arithmetic unchanged, because it counts changes rather than operations.

When randomization is the wrong lever

If the input is known to be well-distributed and the application can tolerate the geometric worst case, a deterministic incremental algorithm with a good ordering heuristic can outperform the randomized one by exploiting locality. The randomized bound is a guarantee about the worst input, and a guarantee is worth less when the input is already known to be benign.

If the structure must be built incrementally as data arrives, with no opportunity to reorder, the randomization must be applied to the insertion sequence itself, which is not always possible. An online setting where points arrive in an order chosen by an adversary is the case the technique cannot address; the analysis requires the order to be random and independent of the data.

If the application requires the exact same output for the same input across runs, the random order must be derived deterministically from the input, for instance by hashing the point coordinates, which restores reproducibility but also restores the adversary’s ability to choose an input that produces a bad order. The guarantee then holds only for inputs the adversary cannot construct.

The last point is the recurring theme of randomized construction: the randomness must be independent of the data for the analysis to apply, and any attempt to make the algorithm deterministic by seeding from the data reintroduces the dependence the randomization was meant to break.