Randomized incremental construction

Consider noncrossing segments in an enclosing rectangle, with no vertical segments and a generic sweep direction; shared endpoints use fixed consistent conventions. A cell of their vertical trapezoidal decomposition is defined by a top segment, a bottom segment, and left and right endpoint-producing segments, with some sides possibly supplied by the enclosing box. At most four input objects define one cell. Removing an object outside that set leaves the cell unchanged, which is the key backward implication.

Condition on the first i inserted objects as an unordered subset. Every object in that subset is equally likely to have been inserted last. Thus a particular resulting cell could have just appeared only if the last object belongs to its defining set. Since the decomposition has only linearly many cells, summing this probability over its cells bounds the expected number newly created by a constant. This uses the canonical geometry of a subset; an insertion-order-dependent tie rule would undermine that conditioning argument.

A history directed acyclic graph replaces a deleted cell's leaf by a small decision structure. For a fixed query independent of the random permutation, its containing cell changes only when one of that cell's defining objects was inserted last. At most a constant number of comparisons is added per change. Summing the inverse-stage probability gives an expected logarithmic path. The same bookkeeping, combined with linear expected total structural changes and appropriate endpoint location, yields expected sorting-scale construction and expected linear storage.

The quantifiers are crucial: a fixed query is arbitrary but selected independently of the algorithm's random choices. Its expected path length does not bound the maximum path of every resulting graph. Achieving simultaneous guaranteed query time can use certification and rebuilding or another point-location method, with a separate proof. Likewise, constant expected update size is not enough to establish total running time if locating the affected feature still scans the whole current structure at each insertion.

In a general-position planar Delaunay triangulation, the graph of a fixed site subset is independent of insertion order. A uniformly random last site has degree equal in expectation to the graph's average degree, which is bounded by a planar-graph constant. An insertion procedure whose local changes are charged to that degree therefore has constant expected structural work, with appropriate handling of hull changes or auxiliary outer vertices. Exact point location and cavity repair remain algorithmic obligations, not consequences of the degree average alone.

With a suitable history or conflict structure, randomized incremental planar Delaunay construction has expected sorting-scale total time. The expectation is over permutations for every fixed admissible input; a bad prescribed order can have quadratic work. Correctness should hold for every order when predicates and tie rules are correct, making this a Las Vegas style use of randomness rather than accepting incorrect geometry with small probability. General-position exclusions can be replaced by a coherent fixed perturbation scheme, but that scheme and its output interpretation must be specified.