Space Efficient Geometric Data Structures

Space-efficient geometric algorithms and data structures

By Ilya Katz and Hervé Brönnimann

template<class RandomAccessIterator, class AxisAlignedGeometry>

void inplaceds::insert_dynamic_kdtree ( RandomAccessIterator first,

RandomAccessIterator last,

AxisAlignedGeometry geom

)

Adds an element to the kd-tree and preserves kd-tree property. The element to be added to the kd-tree is at iterator (last-1) .

Precondition:

Range [first, last-1) must be a valid kd-tree.

Postcondition:

Range [first, last) is a valid kd-tree.

Requirements on types:

Elements must be Assignable [http://www.sgi.com/tech/stl/Assignable.html]

RandomAccessIterator is a model of [http://www.sgi.com/tech/stl/RandomAccessIterator.html]

AxisAlignedGeometry is a geometry kernel

Complexity:
$O(\log{n}^2)$ amortized

Definition at line 95 of file dynamic_kd_tree.hpp.

Code Documentation generated Using Doxygen