Space Efficient Geometric Data Structures

Space-efficient geometric algorithms and data structures

By Ilya Katz and Hervé Brönnimann

template<class Box, class RandomAccessIterator, class OutputIterator, class AxisAlignedGeometry>

OutputIterator inplaceds::window_query_dynamic_kdtree ( RandomAccessIterator first,

RandomAccessIterator last,

AxisAlignedGeometry geom,

Box Q,

OutputIterator result

)

Queries a kd-tree with a box query.

Precondition:

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

Postcondition:

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

Requirements on types:

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

AxisAlignedGeometry is a geometry kernel

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

Box is a class that represents a box

Complexity:
$O((\sqrt{n}+k)\log{n})$ , where $ k $ is the number of points in the box

Definition at line 143 of file dynamic_kd_tree.hpp.

Code Documentation generated Using Doxygen