Other Geometric Structures

Spatial indexes beyond the KD-tree. Most are rare in competitive programming but standard in graphics, GIS and databases.

Quadtree / Octree

Recursively split a square (or cube) into 4 (or 8) equal children, stopping when a cell holds few enough objects.

• Grid-aligned splits, unlike a KD-tree’s median splits — so the structure depends only on the region, not the data.
• Depth depends on how clustered the data is; can degenerate badly.
• Excellent for grids and images where coordinates are bounded integers.

Uses: image compression (region quadtrees), collision broad-phase, terrain LOD, the Barnes-Hut $n$-body approximation, and “compressed 2D grid” problems where most of the grid is empty.

Interval tree

Store intervals; query “which intervals contain point $x$” or “which overlap $[a,b]$”.

Structure: a balanced BST keyed by interval midpoint, with each node storing the intervals crossing its centre, sorted by both endpoints.

• Build $O(n\log n)$, query $O(\log n+\text{output})$, memory $O(n)$.
• In practice, a sweep line with a multiset solves the same problems more simply.

Segment tree (the geometric one)

Confusingly, the original segment tree from computational geometry is different from the competitive programming segment tree. It stores intervals in the $O(\log n)$ canonical nodes covering each, giving stabbing queries in $O(\log n+k)$ with $O(n\log n)$ memory.

The CP version stores an array and answers range aggregates; the geometric version stores intervals and answers point-stabbing. Both are trees over a coordinate range, hence the shared name.

Range tree

A BST over $x$, where each node holds a sorted array of the $y$ values in its subtree.

• Query $O({\log }^{2}n)$ (or $O(\log n)$ with fractional cascading), memory $O(n\log n)$.
• Generalises to $d$ dimensions with $O({\log }^{d}n)$ query and $O(n{\log }^{d-1}n)$ memory.
• This is the merge sort tree under another name.

R-tree

Group nearby objects into minimum bounding rectangles, then group those recursively. Unlike a KD-tree it indexes objects with extent, not just points, and the bounding boxes may overlap.

The standard spatial index in databases (PostGIS, Oracle Spatial, SQLite RTree). Insertion heuristics (R-tree, Hilbert R-tree) matter more than the asymptotics, which have no useful worst-case bound.

Bounding Volume Hierarchy (BVH)

A binary tree of bounding volumes over triangles or objects, built to minimise a surface area heuristic cost. The dominant structure in ray tracing — every production renderer uses one.

Query: descend, pruning any node whose bounding volume the ray misses.

Choosing

Task	Structure
Nearest neighbour, points, low $d$	KD-tree
Rectangle count/sum, offline	BIT sweep — simplest and fastest
Rectangle query, online	persistent segment tree or KD-tree
Which intervals contain $x$	interval tree, or a sweep line
Overlapping rectangles, area of union	sweep line + segment tree with counts
Grid, mostly empty	quadtree, or coordinate compression
Objects with extent, insertions	R-tree
Ray-object intersection	BVH
Nearest neighbour, high $d$	LSH / approximate methods

The contest reality

Almost every geometric query problem in competitive programming is solved by one of three things:

1. Sweep line with a set or a segment tree;
2. Coordinate compression followed by a dense 2D structure;
3. Offline processing sorted by one coordinate, with a BIT over the other.

Reach for a specialised spatial index only when the queries are genuinely online and genuinely geometric.

See also: KD-Tree · Sweep Line · 2D Queries