# Spatial Partitioning with k-d Trees for Nearest Neighbor Queries: A Complete Guide to the shareOI Implementation

> Master spatial partitioning with k-d trees for fast nearest neighbor queries. Explore the hzwer shareOI implementation for efficient O(log n) searches.

- Repository: [hzwer/shareoi](https://github.com/hzwer/shareoi)
- Tags: deep-dive
- Published: 2026-03-03

---

**A k-d tree recursively partitions k-dimensional space using axis-aligned hyperplanes, enabling average-case \(O(\log n)\) nearest-neighbor searches by pruning subtrees that cannot contain closer points.**

The **shareOI** repository is a curated collection of competitive-programming lecture notes and reference materials. Among its data-structure resources, two PDF documents provide comprehensive coverage of **spatial partitioning with k-d trees for nearest neighbor queries**, including construction algorithms, search strategies, and practical OI problem applications.

## What Is a k-d Tree?

A **k-d tree** (k-dimensional tree) is a binary space-partitioning data structure that organizes points in k-dimensional space. In the 2-D case common in competitive programming, each node stores a point \((x, y)\) and a split dimension `d` (where `0` indicates an x-axis split and `1` indicates a y-axis split).

### Construction Process

The tree is built recursively to maintain balance:

1. **Sort** the current point list by the active dimension.
2. **Select the median** as the root node.
3. **Recursively build** left and right subtrees using the remaining points and alternating the dimension.

This median-based approach guarantees a balanced tree with depth approximately \(O(\log n)\) and construction complexity of \(O(n \log n)\), as detailed in `数据结构/k-d Tree_翁家翌.pdf` (page 3-4).

## Nearest Neighbor Search Algorithm

The nearest-neighbor query performs a **recursive depth-first search** with aggressive pruning. The algorithm follows the side of the split containing the query point first, then determines whether the opposite side could contain a closer point.

### Search Steps

1. **Descend** to the leaf following the split dimension (left if query coordinate is less than node coordinate, otherwise right).
2. **Update** the best distance using the current node's point.
3. **Prune** by checking if the perpendicular distance to the splitting line is less than the current best distance. If the hyper-rectangle of the opposite subtree intersects the current best sphere, recurse into that subtree.

This pruning condition—checking whether \((\text{split coordinate} - \text{query coordinate})^2 < \text{bestDist}\)—is the key optimization that reduces average query time to \(O(\log n)\), though worst-case remains \(O(n)\) for degenerate data. This logic is illustrated on page 7 of `数据结构/k-d tree在传统OI数据结构题中的应用_任之洲.pdf`.

## C++ Implementation for Competitive Programming

The shareOI materials provide pseudocode that translates directly into a compact C++17 implementation. Below is a complete 2-D k-d tree supporting static construction and nearest-neighbor queries, following the conventions from the repository's lecture notes:

```cpp
#include <bits/stdc++.h>
using namespace std;

struct KDNode {
    int x, y;               // point coordinates
    int dim;                // split dimension: 0 = x, 1 = y
    KDNode *l = nullptr, *r = nullptr;
};

using ll = long long;

inline ll dist2(const KDNode* a, int qx, int qy) {
    ll dx = (ll)a->x - qx;
    ll dy = (ll)a->y - qy;
    return dx*dx + dy*dy;
}

// Build from a vector of points (static version)
KDNode* build(vector<pair<int,int>>& pts, int l, int r, int dim) {
    if (l > r) return nullptr;
    int m = (l + r) >> 1;
    nth_element(pts.begin() + l, pts.begin() + m, pts.begin() + r + 1,
        [dim](const auto& a, const auto& b) {
            return dim ? a.second < b.second : a.first < b.first;
        });
    KDNode* cur = new KDNode{pts[m].first, pts[m].second, dim};
    cur->l = build(pts, l, m - 1, dim ^ 1);
    cur->r = build(pts, m + 1, r, dim ^ 1);
    return cur;
}

// Recursive nearest neighbor search
void nearest(KDNode* node, int qx, int qy, KDNode*& best, ll& bestDist) {
    if (!node) return;
    
    ll d = dist2(node, qx, qy);
    if (d < bestDist) {
        bestDist = d;
        best = node;
    }
    
    int dim = node->dim;
    KDNode* first = (dim ? qy < node->y : qx < node->x) ? node->l : node->r;
    KDNode* second = (first == node->l) ? node->r : node->l;
    
    nearest(first, qx, qy, best, bestDist);
    
    // Pruning: check if we need to explore the other side
    ll delta = dim ? (ll)node->y - qy : (ll)node->x - qx;
    if (delta * delta < bestDist) {
        nearest(second, qx, qy, best, bestDist);
    }
}

```

### Usage Example

```cpp
int main() {
    vector<pair<int,int>> points = {{1,2}, {3,5}, {7,1}, {4,8}, {2,9}};
    KDNode* root = build(points, 0, (int)points.size() - 1, 0);
    
    int queryX = 4, queryY = 3;
    KDNode* nearestNode = nullptr;
    ll bestDistance = (1LL << 62);
    
    nearest(root, queryX, queryY, nearestNode, bestDistance);
    
    if (nearestNode) {
        cout << "Nearest point: (" << nearestNode->x << ", " << nearestNode->y << ")\n";
        cout << "Squared distance: " << bestDistance << "\n";
    }
    return 0;
}

```

This implementation mirrors the pseudocode found on page 4 of `数据结构/k-d Tree_翁家翌.pdf` and incorporates the pruning optimization detailed on page 7 of `数据结构/k-d tree在传统OI数据结构题中的应用_任之洲.pdf`.

## Key Reference Files in shareOI

The shareOI repository contains two primary documents covering **spatial partitioning with k-d trees for nearest neighbor queries**:

| File | Description | Location |
|------|-------------|----------|
| `数据结构/k-d Tree_翁家翌.pdf` | Foundational slide deck covering k-d tree definition, median-based construction, and the recursive nearest-neighbor search algorithm with complexity proofs. | [View on GitHub](https://github.com/hzwer/shareOI/blob/master/数据结构/k-d%20Tree_%E7%BF%81%E5%AE%B6%E8%BF%9E.pdf) |
| `数据结构/k-d tree在传统OI数据结构题中的应用_任之洲.pdf` | Advanced case studies demonstrating applications to range counting, closest pair problems, and dynamic point insertion with pruning optimizations. | [View on GitHub](https://github.com/hzwer/shareOI/blob/master/数据结构/k-d%20tree%E5%9C%A8%E4%BC%A0%E7%BB%9FOI%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E9%A2%98%E4%B8%AD%E7%9A%84%E5%BA%94%E7%94%A8_%E4%BB%BB%E4%B9%8B%E6%B4%B2.pdf) |

These documents provide the theoretical foundation and practical patterns needed to implement k-d trees for competitive programming contests.

## Summary

- **k-d trees** provide efficient **spatial partitioning** for k-dimensional data by recursively splitting space with axis-aligned hyperplanes.
- **Construction** uses median splitting to guarantee \(O(n \log n)\) build time and balanced \(O(\log n)\) depth.
- **Nearest neighbor queries** achieve \(O(\log n)\) average time through recursive descent and geometric pruning based on splitting line distances.
- The **shareOI** repository contains authoritative reference materials in `数据结构/k-d Tree_翁家翌.pdf` and `数据结构/k-d tree在传统OI数据结构题中的应用_任之洲.pdf` that detail both theory and competitive programming applications.
- A minimal C++17 implementation requires approximately 80 lines of code using `nth_element` for median selection and recursive pruning for efficient queries.

## Frequently Asked Questions

### How does a k-d tree differ from a quadtree or R-tree for spatial partitioning?

A k-d tree uses **axis-aligned binary splits** determined by the median of point coordinates, resulting in a balanced binary tree. Quadtrees recursively partition space into four quadrants regardless of data distribution, which can lead to unbalanced trees with clustered data. R-trees use minimum bounding rectangles (MBRs) optimized for disk-based storage and spatial databases. For in-memory **nearest neighbor queries** in competitive programming, k-d trees offer simpler implementation and better cache locality than R-trees, with more predictable performance than quadtrees.

### What is the worst-case time complexity for nearest neighbor queries in a k-d tree?

While the **average-case query time** is \(O(\log n)\) for randomly distributed data, the **worst-case complexity** is \(O(n)\). This occurs when the query point lies in a region that forces the algorithm to visit every node, such as when all points lie on a circle and the query is at the center, or when the tree becomes unbalanced due to degenerate input data. The pruning optimization—checking whether the splitting line intersects the current best sphere—cannot eliminate subtrees in these pathological cases.

### Can k-d trees handle dynamic insertion and deletion of points?

Yes, though with caveats. The static construction method shown in `数据结构/k-d Tree_翁家翌.pdf` builds a perfectly balanced tree from a fixed point set using median selection. For **dynamic insertion**, you can insert points by traversing the tree as in a binary search tree and placing the new point at a leaf, but this may gradually unbalance the tree. The second PDF `数据结构/k-d tree在传统OI数据结构题中的应用_任之洲.pdf` discusses **rebuilding strategies**—periodically reconstructing the entire subtree when its size doubles or when imbalance exceeds a threshold—to maintain \(O(\log n)\) query performance in dynamic scenarios.

### Why are k-d trees preferred over brute-force methods for nearest neighbor problems in OI contests?

In competitive programming contests, **k-d trees reduce the time complexity** of nearest neighbor queries from \(O(n)\) per query (brute-force) to \(O(\log n)\) on average. For problems with \(10^5\) points and \(10^5\) queries, brute-force methods result in \(10^{10}\) operations, which will time out, whereas a k-d tree handles the same constraints within milliseconds. Additionally, the implementation is relatively compact (under 100 lines of C++), requires no external libraries, and handles 2-D geometric problems naturally, making it a standard tool in the OI data structure repertoire documented in the shareOI repository.