DSA DSA In Depth
0%
From-Scratch Build

Multi-Dimensional k-d Tree with Branch-and-Bound k-NN & Range Search

A balanced multi-dimensional k-d Tree supporting orthogonal bounding-box range queries and branch-and-bound 1-NN / k-NN search with hypersphere-hyperplane pruning telemetry.

~45 min Advanced Lessons: Build Lab: 2D/3D k-d Tree with Bounding-Box Pruning for K-Nearest Neighbor & Range Search, Multidimensional Spatial Indexing: k-d Trees, Quadtrees, R-Trees & Z-Order (Morton) Curves, Branch and Bound: Best-First / DFS Relaxation Bounds for Combinatorial Optimization, Order Statistics: Randomized Quickselect vs Deterministic BFPRT Median-of-Medians, Binary & d-ary Heaps: Floyd's O(N) Bottom-Up Build-Heap Proof, Augmenting BSTs: Order-Statistic Trees (select/rank) & Interval Trees
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

Spatial Partitioning via Alternating Hyperplanes

A $k$-d Tree ($k$-dimensional tree) is a binary space-partitioning tree where each internal node at depth $d$ splits space with an axis-aligned hyperplane perpendicular to coordinate axis $a = d \bmod k$. Choosing the median point along axis $a$ guarantees a balanced tree of height $\lceil \log_2(n + 1) \rceil$ built in $O(n \log n)$ time.

Branch-and-Bound Hypersphere Pruning

Given a query point $q$, how do we find its exact nearest neighbor without scanning all $n$ points?

  1. Maintain a running candidate ball of radius $R = \text{bestDist}$ centered at $q$.
  2. At any splitting node $p$ on axis $a$, compute the perpendicular distance from $q$ to the splitting hyperplane: $$\Delta_a = |q[a] - p[a]|$$
  3. Always search the near half-space first (the side of the hyperplane containing $q$). This rapidly shrinks $R$.
  4. Prune the far half-space whenever $\Delta_a \ge R$ (equivalently $\Delta_a^2 \ge R^2$, avoiding square roots). Geometrically, if the query hypersphere of radius $R$ does not intersect the splitting hyperplane, no point on the far side can possibly be closer than our current best!

Curriculum Connections

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Alternating-Axis Median Partitioning

  • Core Mechanical Concept: Alternating-Axis Median Partitioning
  • Target Module: index.js (Step1)
  • Engineering Specification: At depth $d$, select splitting axis $\text{axis} = d \bmod k$, sort points along that coordinate, pick the median as the splitting hyperplane, and recursively build left and right subtrees.
  • Verification Invariant: verifies Step 1: Alternating-Axis Median Partitioning

Step 2: Orthogonal Bounding-Box Range Search

  • Core Mechanical Concept: Orthogonal Bounding-Box Range Search
  • Target Module: index.js (Step2)
  • Engineering Specification: Implement rangeSearch(minBounds, maxBounds) by pruning the left half-space when minBounds[axis] > node.point[axis] and pruning the right half-space when maxBounds[axis] < node.point[axis].
  • Verification Invariant: verifies Step 2: Orthogonal Bounding-Box Range Search

Step 3: Branch-and-Bound Nearest Neighbor Pruning

  • Core Mechanical Concept: Branch-and-Bound Nearest Neighbor Pruning
  • Target Module: index.js (Step3)
  • Engineering Specification: Always recurse into the near child containing target first to shrink bestSq quickly. Only recurse into the far child if the perpendicular distance to the splitting hyperplane satisfies $(target[axis] - node.point[axis])^2 < bestSq$.
  • Verification Invariant: verifies Step 3: Branch-and-Bound Nearest Neighbor Pruning

Step 4: Bounded k-Nearest Neighbors (k-NN)

  • Core Mechanical Concept: Bounded k-Nearest Neighbors (k-NN)
  • Target Module: index.js (Step4)
  • Engineering Specification: Generalize pruning to $k$ nearest neighbors by comparing the hyperplane distance against the $k$-th best squared distance collected so far.
  • Verification Invariant: verifies Step 4: Bounded k-Nearest Neighbors (k-NN)

Asymptotic & Memory Layout Guarantees

  • Category: Computational Geometry & Spatial Indexing
  • Difficulty: Advanced (~45 minutes)
  • Key Architectural Highlights:
    • Alternating-axis median partitioning building a balanced k-d tree
    • Branch-and-Bound Nearest Neighbor pruning the far half-space when axisDist^2 >= bestDist^2
    • Bounded Max-Heap k-Nearest Neighbors (k-NN) and orthogonal hyper-rectangle range queries
  • Tags & Primitives: k-d Tree, Spatial Indexing, Branch-and-Bound k-NN, Orthogonal Range Search, Hypersphere Pruning

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.