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::remove_dynamic_kdtree ( RandomAccessIterator first,

RandomAccessIterator pos,

RandomAccessIterator last,

AxisAlignedGeometry geom

)

Removes an element from the kd-tree.

Precondition:

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

Postcondition:

Range [first, last-1) 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 232 of file dynamic_kd_tree.hpp.

Code Documentation generated Using Doxygen