Trapezoidal Maps and Randomized Point Location

Trapezoidal Maps and Randomized Point Location

Part 14 organized space by repeatedly splitting boxes. That works beautifully when the boxes themselves are the abstraction. A planar subdivision asks a sharper question: given a query point $q$, which face contains it? Roads, parcel boundaries, visibility maps, and arrangements all need this planar point-location operation. Scanning every edge costs $O(n)$ per query. Here we build a linear-size search structure with expected $O(\log n)$ query time by allowing the input segments—not a fixed grid—to shape the cells.

The construction has two layers. A trapezoidal map vertically decomposes the free space around noncrossing segments. A persistent history DAG remembers how cells were replaced during randomized incremental insertion. The map describes the current geometry; the DAG answers future questions.

From Subdivision Faces to Vertical Cells

Assume first that the input is a planar straight-line graph: segment interiors do not cross, and no segment is vertical. Enclose it in a large bounding rectangle. From every segment endpoint, shoot a vertical ray upward and another downward until each hits another segment or the bounding box. The resulting cells are called trapezoids, although a cell may degenerate to a triangle when one vertical side has zero length.

Each trapezoid stores four kinds of boundary information:

• a top segment and a bottom segment;
• a left endpoint and a right endpoint defining its vertical extent;
• up to two neighbors across each vertical side.

The top and bottom need not be parallel. What matters is that every vertical line intersects a cell in a single interval. This $x$-monotonicity makes local navigation possible.

For $n$ noncrossing segments, this decomposition has $O(n)$ cells: every endpoint starts only two vertical extensions, and planar adjacency limits the number of resulting pieces. The decomposition alone, however, is not yet a fast index. We still need a way to choose the right cell without scanning them.

Insert Segments in Random Order

Start with one cell: the bounding rectangle. Choose a uniformly random permutation of the segments and insert them one at a time. To insert segment $s=\overline{pq}$, orient it so $p$ is lexicographically before $q$ and perform three tasks:

1. locate the trapezoid containing $p$;
2. walk through every trapezoid crossed by $s$;
3. replace those old cells with the new cells above, below, left of, and right of $s$.

Locating $p$ uses the history DAG already built. To find subsequent crossed cells, do not restart a global query. At the current cell's right boundary, compare $s$ with the endpoint that created the vertical wall. If the endpoint lies above $s$, continue through the lower-right neighbor; otherwise use the upper-right neighbor. Because $s$ is $x$-monotone and does not cross existing segments, this walk visits crossed cells from left to right exactly once.

The first and last crossed cells may leave a remainder to the left of $p$ or right of $q$. Each crossed cell also contributes a piece above and below $s$. Adjacent upper pieces with the same top boundary are merged; likewise for lower pieces with the same bottom boundary. Without merging, the representation retains artificial walls and can grow far beyond the true trapezoidal map.

A Search Structure That Remembers Replacements

Deleting an old trapezoid from the current map must not delete its search history. Instead, its leaf in the search structure is replaced by a small decision graph. There are three node types:

• an X-node stores an endpoint $p$ and asks whether $q_x \lt p_x$;
• a Y-node stores a segment $s$ and asks whether $q$ lies above or below $s$;
• a leaf points to a current trapezoid.

An insertion confined to one trapezoid may replace its leaf by X-nodes for $p$ and $q$ with a Y-node between them. A segment crossing multiple cells replaces several leaves with suitable Y-nodes and endpoint tests. Merging makes this structure a DAG rather than a tree: several historical paths can lead to the same current trapezoid leaf.

A query starts at the root. At an X-node it branches left or right by endpoint order. At a Y-node it evaluates an orientation predicate against the stored segment. Reaching a leaf identifies the containing trapezoid, whose face label identifies the subdivision face.

The DAG must use the same boundary convention as construction. If $q$ lies on an endpoint or segment, the application may report ON_VERTEX or ON_EDGE immediately; otherwise a symbolic tie-break consistently sends it to one adjacent open cell.

Reference Mechanics

The following Python-like scaffold exposes the control flow. Production code must also maintain all neighbor pointers and replace every historical leaf that referenced an obsolete cell.

def orient(a, b, q):
    return (b.x-a.x) * (q.y-a.y) - (b.y-a.y) * (q.x-a.x)

def locate(root, q):
    node = root
    while node.kind != "leaf":
        if node.kind == "x":
            # Lexicographic tie-break makes equal x-coordinates total.
            node = node.left if (q.x, q.y) < (node.p.x, node.p.y) else node.right
        else:                       # Y-node
            side = orient(node.seg.left, node.seg.right, q)
            if side == 0:
                return ("ON_EDGE", node.seg)
            node = node.above if side > 0 else node.below
    return ("CELL", node.trapezoid)

def crossed_trapezoids(root, s):
    t = locate(root, s.left)[1]
    out = [t]
    while s.right.x > t.right_site.x:
        wall_site = t.right_site
        # s cannot cross an existing segment, so one neighbor continues it.
        t = t.lower_right if orient(s.left, s.right, wall_site) > 0 \
                          else t.upper_right
        out.append(t)
    return out

def incremental_map(segments, rng):
    root, current_map = bounding_box_leaf(), initial_map()
    for s in rng.permutation(segments):
        chain = crossed_trapezoids(root, s)
        new_cells = split_and_merge(chain, s)
        reconnect_neighbors(chain, new_cells)
        root = replace_history_leaves(root, chain, new_cells, s)
    return current_map, root

Notice that orient is the decisive geometric predicate. Computing a slope or the $y$-coordinate of a line at $q_x$ introduces division and awkward vertical cases; orientation is algebraic, sign-based, and amenable to exact arithmetic.

Why the Expected Bounds Are Small

The final trapezoidal map has $O(n)$ cells, but the history DAG also contains cells that once existed and were later replaced. Random order keeps their expected total at $O(n)$. Construction takes expected $O(n\log n)$ time, uses expected $O(n)$ space, and answers a point-location query in expected $O(\log n)$ time.

The intuition comes from backward analysis. Imagine deleting the last inserted segment from a completed random prefix of $i$ segments. Only features adjacent to that uniformly random segment disappear. Since the map has only linear complexity, the average number of affected features is constant. Reading the process forward, insertion therefore creates only $O(1)$ expected new structural complexity, even though an unlucky segment can cross many current cells.

For a fixed query point, reverse the random history again. At stage $i$, the probability that the newly exposed segment changes the query's remembered cell is $O(1/i)$. Summing $1/i$ gives $O(\log n)$ expected search depth. Stronger high-probability statements follow by rebuilding when the DAG is unexpectedly deep or large: bad permutations exist, but their tail probability falls quickly enough that restart is a practical guardrail. “Expected” is over preprocessing randomness for any fixed input and query—not over a friendly distribution of coordinates.

Degeneracies Need a Policy, Not Hope

Textbook general position hides cases that real data contains. Decide these policies before building:

• Vertical segments: rotate or shear coordinates symbolically, or implement a symmetric rule that treats vertical input edges as barriers rather than vertical decomposition walls. Never divide by $\Delta x$.
• Shared endpoints: group incident segments by exact endpoint identity and order them radially with orientation predicates. Do not create separate zero-width walls for the same site.
• Coincident or overlapping segments: normalize endpoint order, detect collinear interval overlap, and either merge duplicates while retaining source labels or reject non-PSLG input. The basic algorithm assumes interiors are disjoint.
• Equal $x$-coordinates: use a consistent lexicographic or symbolic perturbation order for X-node decisions and wall events.
• Boundary queries: return a three-way classification—face, edge, or vertex—rather than forcing every boundary point into an arbitrary face.

Use exact integer orientation when coordinates and products fit a widened integer type; otherwise use adaptive exact predicates. Epsilon comparisons are dangerous in the DAG because “approximately left” and “approximately above” can become non-transitive across nodes. Separate robust predicates from approximate constructions: topology follows certified signs, while display coordinates may remain floating point. After every split, audit reciprocal neighbor links, top/bottom incidence, positive $x$-extent except documented degeneracies, and the rule that every live leaf references exactly one current cell.

When to Use Another Index

Slabs are attractive when the subdivision has few distinct vertex $x$-coordinates or simplicity matters more than memory. Triangulation-based hierarchies fit pipelines that already triangulate faces and want deterministic guarantees. Trapezoidal maps are compelling for static noncrossing segments when linear expected space, output-sensitive insertion walks, and a direct geometric search history align with the application.

The broader lesson is not merely “shuffle the segments.” It is to preserve just enough obsolete structure to route future queries, while random order limits how much obsolete structure accumulates. The Randomized Algorithms deep dive develops backward analysis, conflict graphs, verification, and restart strategies as a reusable design pattern. Part 16 applies geometric structure to proximity: instead of asking which subdivision face contains $q$, we build the subdivision whose faces encode which site is nearest.