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