Navigation: Up, Table of Contents, Bibliography, Index, Title Page

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

| advanced |

Next: Pm_naive_point_location<Planar_map>

Navigation: Table of Contents, Bibliography, Index, Title Page

The CGAL Project . Tue, December 21, 2004 .