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

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:

#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

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
数据结构/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

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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}