begin of advanced section  advanced  begin of advanced section



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


Inherits From



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