kD-Tree Hierarchy of axis-aligned partitions ° 2-D partitions are lines ° 3-D partitions are planes Axis of partitions alternates wrt depth of the tree Average access time is O(log n) Worst case O(n) when tree is severely lopsided Need to maintain a balanced tree O(n log n) Can find k nearest neighbors in O(k + log n) time using a heap
{}