advanced

CGAL::Pm_trapezoid_ric_point_location<Planar_map>

Definition

The Pm_trapezoid_ric_point_location<Planar_map> class implements the incremental randomized algorithm introduced by Mulmuley  [Mul90] as presented by Seidel  [Sei91], [dBvKOS97]. It uses a trapezoidal map and a search structure to achieve an expected query time of $$O(log$$n). Updating of these structures takes expected $$O(log$$n) time. There is also a possibility to assure a deterministic worst-case query time of $$O(log$$n), with a preprocessing step. The trade-off is in a longer building time.

#include <CGAL/Pm_trapezoid_ric_point_location.h>

Is Model for the Concept

PlanarMapPointLocation_2

Inherits From

Pm_point_location_base<Planar_map>

Creation

Pm_trapezoid_ric_point_location<Planar_map> pl ( bool preprocess = false);
	constructs the point location object. If preprocess is true then preprocessing is done to guarantee a deterministic worst case query time of $$O(log$$n). However, the preprocessing step can slow down considerably the building time of the structure.

See Also

Discussion of the different point location strategies in the introduction of Planar_map reference pages.

advanced