Simplex Range Searching and Partition Trees

Simplex Range Searching and Partition Trees

Part 12 matched query shapes to specialized structures: intervals for stabbing, segment trees for canonical intervals, and priority search trees for three-sided windows. Those structures exploit coordinate alignment. A rectangular query can be peeled apart one coordinate at a time because its inequalities are independent: $a_i \le x_i \le b_i$.

A triangle is different. Each side is an oblique linear inequality, and rotating the triangle changes all coordinate comparisons. Simplex range searching asks us to preprocess a point set $P\subset\mathbb{R}^d$ so that, for a query simplex $\sigma$, we can count, aggregate, or report the points in $P\cap\sigma$. In the plane the simplex is a triangle; in three dimensions it is a tetrahedron. More generally, a $d$-simplex is the intersection of $d+1$ halfspaces.

That last description is the key. We stop organizing points by vertical and horizontal slabs and instead organize them into spatial groups that arbitrary hyperplanes cross only sparingly.

Boxes, Halfspaces, and Simplices

An orthogonal box has $2d$ axis-aligned facets. A range tree turns those coordinate bounds into nested one-dimensional searches. A halfspace has one arbitrarily oriented boundary hyperplane; a simplex combines a constant number of such halfspaces. This difference changes which decomposition is useful.

A triangle query can test a point with three orientation signs. But testing all $n$ points costs $O(n)$. A partition tree lifts those point tests to groups. Each node stores a subset $P_v$ and a simple region containing it. If the query contains that region, its stored count can be added at once. If the region is disjoint, it contributes nothing. Only an ambiguous, crossed region causes descent.

A Simplicial Partition

Choose a parameter $r$. A simplicial $r$-partition splits $P$ into $t=O(r)$ subsets $P_1,\ldots,P_t$, each of size between constant multiples of $n/r$, and associates each subset with a simplex $\Delta_i$ containing it. The essential guarantee is a low crossing number: every hyperplane intersects the interior of only $O(r^{1-1/d})$ partition simplices. In the plane, a line crosses only $O(\sqrt r)$ triangles, rather than all $r$ of them.

The cells may overlap, and a cell may contain empty space or points belonging to another group. This is not a mesh. Membership belongs to the subsets; the enclosing simplices exist to certify whole-group acceptance and to bound boundary crossings.

Why is the exponent $1-1/d$ plausible? Imagine $r$ roughly round cells arranged as a $d$-dimensional grid. There are about $r^{1/d}$ cells along each axis. A hyperplane behaves like a $(d-1)$-dimensional sheet, so it meets about $(r^{1/d})^{d-1}=r^{1-1/d}$ cells. Simplicial partition theorems obtain a comparable guarantee without assuming a friendly grid or uniform data.

Recursing into a Partition Tree

Build a root for all points, compute an $r$-partition, and recurse on every subset until a leaf holds a small constant number of points. Store at each node the subset's count—or a commutative aggregate such as total weight—and the simplex associated with every child.

For a halfspace query $H$, classify each child simplex $\Delta$:

1. If $\Delta\subseteq H$, add the child's aggregate.
2. If $\Delta\cap H=\varnothing$, discard it.
3. If the boundary hyperplane crosses $\Delta$, recurse.

A simplex query applies the same logic against all $d+1$ facets. A cell is accepted only if it lies inside every halfspace; it is rejected if separated by any one; otherwise it is crossed. Since the number of facets is constant for fixed $d$, it changes constants rather than the main exponent.

def report_simplex(node, query, output):
    """Conceptual traversal; geometry predicates are supplied by query."""
    if node.is_leaf:
        for point in node.points:
            if query.contains_point(point):
                output.append(point)
        return

    for child in node.children:
        relation = query.classify_simplex(child.cell)
        if relation == "INSIDE":
            # For reporting, enumerate this canonical subtree.
            output.extend(child.all_points())
        elif relation == "CROSSED":
            report_simplex(child, query, output)
        # OUTSIDE contributes nothing.

The pseudocode exposes an important distinction. For counting, an inside node contributes in $O(1)$ from its stored count. For reporting, its points still must be emitted. The typical bound therefore ends in $+k$, where $k=|P\cap\sigma|$. Under standard linear-space partition-tree results, planar simplex queries can be answered in roughly $O(\sqrt n+k)$ time; in fixed dimension $d$, the characteristic term is $O(n^{1-1/d}+k)$, with theorem-specific lower-order factors and construction assumptions.

Query Decomposition as a Frontier

It helps to picture the answer not as a list of visited leaves but as a canonical decomposition. The traversal produces a frontier of fully contained subtrees plus a small residue of boundary leaves. Every reported point belongs to exactly one accepted subtree or residue test.

The crossing-number guarantee controls the amber frontier. A loose bounding box would be poor here: an oblique query line can enter a box even when it misses the point group, producing needless recursion. The enclosing simplices and the partition theorem are chosen together.

Multilevel Trees and Cuttings

Some queries combine several range conditions. A multilevel partition tree stores a secondary structure on each canonical subset: filter by one condition, then search the resulting canonical groups by the next. This resembles layered range trees, but each level uses geometric partitions rather than a coordinate ordering. The benefit is expressiveness; the cost is multiplied storage, preprocessing, constants, and often logarithmic or small-exponent factors. “Add another level” is mathematically clean and frequently impractical.

A related decomposition is a cutting. Given a collection of hyperplanes, a $(1/r)$-cutting divides space into simple cells so that each cell is crossed by at most a $1/r$ fraction of the hyperplanes. Partition trees group points so a query hyperplane crosses few groups; cuttings divide space so each cell conflicts with few input hyperplanes. Through geometric duality, the ideas mirror each other. Cuttings support incidence searching, arrangements, point location, and recursive algorithms in which a cell carries only its conflict list.

Trading Space for Query Time

Linear space and $n^{1-1/d}$ query time are a landmark, not the only operating point. More preprocessing and replicated canonical subsets can reduce query time; less space or simpler partitions can increase it. Exact bounds depend on the range family, semigroup versus reporting model, deterministic versus randomized construction, and dimension, so a claimed tradeoff should name its theorem and model.

In higher dimensions, the exponent deteriorates: $n^{1-1/d}$ approaches $n$ as $d$ grows. Constants also explode because cells have more facets, simplex classification costs more, and multilevel structures replicate data. These are fixed-dimensional techniques, not a cure for generic high-dimensional search.

Practical implementations face further friction:

• Robustly classify a simplex against halfspaces using consistent orientation or determinant signs; an epsilon can make a cell simultaneously “inside” and “outside” across facets.
• Keep boundary semantics explicit. Closed ranges report points on facets; open ranges do not. Exact zero signs need a deterministic policy.
• Favor simpler kd-trees when approximate answers, benign data, or axis-aligned boxes dominate.
• Measure construction cost and memory locality. A theoretically optimal partition can be harder to build and traverse than a coarser hierarchy.
• Preserve $+k$ in reporting claims. No data structure can write $k$ distinct answers in sublinear output time.

What to Carry Forward

Partition trees replace coordinate separability with a boundary-crossing invariant. They group points into balanced subsets, wrap those subsets in simplices, and make a query pay mainly for cells cut by its facets. Multilevel variants compose constraints; cuttings reverse the viewpoint by limiting how many input hyperplanes conflict with each spatial cell.

Part 14 shifts from query-shaped theoretical partitions to an explicitly spatial hierarchy: quadtrees. There, recursive cells are axis-aligned and locality, compression, neighbor finding, and mesh quality take center stage. The comparison is useful: partition trees are engineered around worst-case range-query crossings, while quadtrees are engineered around adaptive resolution of space.