kd_tree.hpp File Reference

k-nearest-neighbor search: median-split kd-tree with contiguous leaf blocks. More...

#include <algorithm>
#include <limits>
#include <numeric>
#include <queue>
#include <stdexcept>
#include <utility>
#include <vector>
#include <Eigen/Dense>
#include "ellipsoid_tree/detail/parallel_for.hpp"

Classes
class	ellipsoid_tree::KDTree
	k-nearest-neighbor kd-tree over a fixed set of points. More...

Namespaces
namespace	ellipsoid_tree

Detailed Description

k-nearest-neighbor search: median-split kd-tree with contiguous leaf blocks.

Points are stored permuted into tree order so leaf blocks scan linearly; the median point of each internal range doubles as its splitting plane. Build is O(n log n) via nth_element.