![]() |
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 log time, where is the complexity of the arrangement.
Constructing the search structures takes log 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>