begin of advanced section  advanced  begin of advanced section

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(logn). Updating of these structures takes expected O(logn) time. There is also a possibility to assure a deterministic worst-case query time of O(logn), 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(logn). 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.

end of advanced section  advanced  end of advanced section