Space-efficient geometric algorithms and data structures

By Ilya Katz and Hervé Brönnimann

dynamic_kd_tree.hpp File Reference

Detailed Description

This is a dynamic version of the static_kd_tree. It supports insertion and deletion. Dynamic operations are accomplished in good amortized time by using the decomposition principle.

ILYA: THIS DOESN"T HELP MUCH. CAN YOU EXPLAIN THE DECOMPOSITION PRINCIPLE, OR AT LEAST PROVIDE A REFERENCE?

Definition in file dynamic_kd_tree.hpp.

Go to the source code of this file.

Namespaces

namespace inplaceds

Functions

template<class RandomAccessIterator, class AxisAlignedGeometry>

void inplaceds::build_dynamic_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom)

Returns true if [first, last) is a valid kd-tree data structure.

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) .

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.

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

OutputIterator inplaceds::halfplane_query_dynamic_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom, Halfplane Q, OutputIterator result)

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.

Code Documentation generated Using Doxygen


Namespaces
namespace	inplaceds
Functions
template<class RandomAccessIterator, class AxisAlignedGeometry>
void	inplaceds::build_dynamic_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom)
	Returns true if [`first`, `last`) is a valid kd-tree data structure.
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) .
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.
template<class Halfplane, class RandomAccessIterator, class OutputIterator, class AxisAlignedGeometry>
OutputIterator	inplaceds::halfplane_query_dynamic_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom, Halfplane Q, OutputIterator result)
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.