|
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 pseudo-trapezoidal cells, each of constant complexity, and constructs and maintains a linear-size 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) expected time and may require a small number of rebuilds [HKH12]. Therefore 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 through 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.
This strategy supports arbitrary subdivisions, including unbounded ones.
#include <CGAL/Arr_trapezoid_ric_point_location.h>
| Arr_trapezoid_ric_point_location<Arrangement> pl ( bool with_guarantees = true); | |
|
If with_guarantees is set to true, the cunstruction performs rebuilds in order to guarantee a resulting structure with linear size and logarithmic query time. Otherwise the structure has expected linear size and expected logarithmic query time.
| |
| Arr_trapezoid_ric_point_location<Arrangement> pl ( Arrangement arr, bool with_guarantees = true); | |
|
Constructs a point location search structure for the given arrangement. If with_guarantees is set to true, the cunstruction performs rebuilds in order to guarantee a resulting structure with linear size and logarithmic query time. Otherwise the structure has expected linear size and expected logarithmic query time.
| |