
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 worstcase query
time of
$$O(log
$$n), with a preprocessing step. The tradeoff 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

