Interval, Segment, and Priority Search Trees

Interval, Segment, and Priority Search Trees

Part 11 organized points so an axis-aligned rectangle could be answered without inspecting the whole plane. This part changes the stored objects and, with them, the useful queries. A horizontal window may ask which time intervals are active, which segments cross it, or which points lie below a ceiling while remaining between two vertical walls. Those sound similar, but each exposes a different kind of order.

The central idea is canonical storage: decompose a query into a small collection of precomputed groups, then report or combine only those groups. Interval trees use a separating coordinate, segment trees use canonical nodes of an elementary-interval hierarchy, and priority search trees combine a search-tree order with a heap priority. Part 13 will generalize this decomposition instinct from rectangular windows to triangles and other simplices.

Three query shapes

Let an interval be \(I=[\ell,r]\), a segment be a geometric line segment in the plane, and a point be \(p=(x,y)\). Common range-searching questions include:

• stabbing: report every interval containing a query coordinate \(q\);
• overlap: report every interval intersecting a query interval \([a,b]\);
• windowing: report objects intersecting an axis-aligned rectangle;
• three-sided reporting: report points in \([a,b]\times(-\infty,c]\).

If \(k\) answers are reported, any algorithm needs \(\Omega(k)\) time just to emit them. Thus bounds such as \(O(\log n+k)\) are output-sensitive: the logarithmic term is navigation, and the \(k\) term is unavoidable output.

Interval trees: divide intervals by a center

A centered interval tree chooses a coordinate \(m\), often the median of all endpoints, and partitions intervals into three sets. Intervals completely left of \(m\) recurse left; intervals completely right recurse right; intervals containing \(m\) stay at the current node. Store those crossing intervals twice: once ordered by left endpoint and once by right endpoint.

For a stabbing query $q < m$, every stored interval already reaches $m$. It contains $q$ exactly when its left endpoint is at most $q$, so scan the left-endpoint ordering until that condition fails, then recurse left. The case $q > m$ is symmetric, using decreasing right endpoints. When $q = m$, every interval stored at the node is an answer.

The tree has linear space because each interval is assigned to exactly one node (the two orderings merely duplicate references). With presorted endpoint lists, construction takes \(O(n\log n)\); stabbing reports in \(O(\log n+k)\). Overlap with \([a,b]\) can be reduced conceptually to endpoints and stabbing, or supported directly: at a node, report crossing intervals that can meet the query and recurse into every side the query reaches. Careful implementations retain \(O(\log n+k)\) reporting with appropriate auxiliary orderings.

Endpoints need a policy

For closed intervals, \([1,3]\) and \([3,5]\) overlap at 3; for half-open intervals, \([1,3)\) and \([3,5)\) do not. Encode endpoints as events such as \((x,\text{kind})\), with an explicit tie order. Do not hide this choice inside floating-point comparisons. Zero-length closed intervals are legitimate points; empty half-open intervals should normally be discarded.

Geometric segment trees: store canonical coverage

A geometric segment tree starts from the sorted distinct x-coordinates of all interval endpoints. Consecutive coordinates—and often the singleton endpoints between them—form elementary intervals. A balanced binary tree groups adjacent elementary intervals. For an input interval \(I\), store a reference at every maximal node whose represented range lies inside \(I\) but whose parent range does not. These are its canonical nodes.

An interval has only \(O(\log n)\) canonical nodes: at any tree depth there are at most two partially exposed boundary paths. Therefore storing \(n\) intervals takes \(O(n\log n)\) references and construction takes \(O(n\log n)\). A stabbing query follows one root-to-leaf path and reports every stored list along it, yielding \(O(\log n+k)\).

For planar line segments, build the tree on their x-projections. At each canonical node, store segments that span its slab, ordered or organized by their vertical behavior. A rectangular window \([x_1,x_2]\times[y_1,y_2]\) decomposes its x-range into canonical nodes, then searches the associated y-structures. The exact bound depends on the secondary structure and whether segments cross; the segment tree supplies the reusable x-decomposition, not a complete intersection algorithm by itself.

Priority search trees: one tree, two orders

A priority search tree (PST) supports three-sided queries \([a,b]\times(-\infty,c]\). It combines:

• binary-search-tree partitioning by x, so \([a,b]\) becomes two boundary paths plus covered subtrees;
• min-heap order by y, so a subtree can be pruned as soon as its minimum y exceeds \(c\).

One common static construction selects the point with minimum y for the node, splits the remaining points near their median x, and recurses. Each point is stored once, giving \(O(n)\) space. Straightforward median selection builds in \(O(n\log n)\), while careful selection and presorted data can achieve linear construction. Reporting takes \(O(\log n+k)\): find the x split, explore the two boundary paths, and recursively report any fully x-contained subtree, stopping wherever the heap minimum is too high.

Three-sided reporting in a conceptual priority search tree

def report_subtree(node, y_max, out):
    if node is None or node.min_y > y_max:
        return                      # heap certificate prunes everything below
    if node.point.y <= y_max:
        out.append(node.point)
    report_subtree(node.left, y_max, out)
    report_subtree(node.right, y_max, out)

def query(node, x_lo, x_hi, y_max, out):
    if node is None or node.min_y > y_max:
        return
    if node.x_max < x_lo or x_hi < node.x_min:
        return                      # outside the vertical strip
    if x_lo <= node.x_min and node.x_max <= x_hi:
        report_subtree(node, y_max, out)
        return
    if x_lo <= node.point.x <= x_hi and node.point.y <= y_max:
        out.append(node.point)
    query(node.left, x_lo, x_hi, y_max, out)
    query(node.right, x_lo, x_hi, y_max, out)

The code shows the certificates clearly, though production PSTs encode x-split ranges implicitly and avoid testing a reported point twice. Flipping y produces an upper-unbounded query; mirroring x handles the corresponding orientations. A four-sided rectangle can be decomposed using richer range structures from Part 11, or sometimes answered through combinations of three-sided searches, but a PST’s sharp guarantee belongs to the three-sided shape.

Which tree fits?

Windowing as a decomposition pipeline

Window queries appear in map viewers, timelines, editors, collision broad phases, and database indexes. A robust design separates responsibilities:

1. Use x to identify a small family of slabs or canonical groups.
2. Within each group, use y-order, endpoint order, or a secondary index.
3. Filter exact geometry last, especially for non-axis-aligned segments.

This prevents a common mistake: treating an overlap of bounding boxes as proof that two geometric objects intersect. Bounding boxes are excellent rejection filters, but exact orientation and incidence predicates decide the final answer.

Degeneracies and engineering details

Coordinate compression must preserve gaps and endpoints. If stabbing at an endpoint matters, leaves representing only open gaps are insufficient; include singleton elementary intervals or use a consistent event ranking. Duplicate endpoints should map to one coordinate, while duplicate objects need stable identifiers if all copies must be reported.

For floating-point input, do not create an arbitrary epsilon-based total order: it can make comparisons non-transitive and corrupt tree invariants. Prefer exact integer/rational coordinates when available, or centralize robust comparisons and define what “touching” means for the application. Normalize reversed intervals so \(\ell\le r\). Decide whether invalid, empty, and infinite intervals are accepted before construction.

Dynamic updates also change the choice. Balanced interval trees can support insertions and deletions with augmented fields; dynamic segment trees may allocate nodes lazily when the coordinate universe is huge; dynamic PSTs require more intricate balancing. State whether coordinates are known offline, whether reports can contain duplicates, and whether the output must be sorted—sorting \(k\) reported items costs an additional \(O(k\log k)\).

From rectangular order to arbitrary query boundaries

Interval, segment, and priority search trees succeed because their query boundaries align with one or two coordinate orders. They turn a window into a logarithmic number of canonical subproblems and attach just enough auxiliary order to each one. The next challenge removes that alignment: Part 13 asks for points inside triangles and simplices. There, median slabs are no longer enough; partition trees, cuttings, and multilevel structures carry the same canonical-decomposition philosophy into oblique geometry.