## CGAL::Arr_trapezoid_ric_point_location<Arrangement>

### Definition

The *Arr_trapezoid_ric_point_location<Arrangement>* class implements the incremental randomized algorithm
introduced by Mulmuley [Mul90] as presented by
Seidel [Sei91] (see also [dBvKOS00, Chapter 6]).
It subdivides each arrangement face to pseuso-trapezoidal cells, each
of constant complexity, and constructs and maintains a search
structure on top of these cells, such that each query can be answered
in $$*O(*log$$*n)* time, where $$*n* is the complexity of the arrangement.

Constructing the search structures takes $$*O(n *log$$*n)* time, such that
attaching a trapezoidal point-location object to an existing arrangement
may incur some overhead in running times. In addition, the point-location
object needs to keep its auxiliary data structures up-to-date as the
arrangement goes thorugh structural changes. It is therefore recommended
to use this point-location strategy for static arrangements (or arrangement
that do not alter frequently), and when the number of issued queries
is relatively large.

*#include <CGAL/Arr_trapezoid_ric_point_location.h>*

### Is Model for the Concepts

*ArrangementPointLocation_2*

*ArrangementVerticalRayShoot_2*