Improved implementation of point location in general two-dimensional subdivisions
From MaRDI portal
Abstract: We present a major revamp of the point-location data structure for general two-dimensional subdivisions via randomized incremental construction, implemented in CGAL, the Computational Geometry Algorithms Library. We can now guarantee that the constructed directed acyclic graph G is of linear size and provides logarithmic query time. Via the construction of the Voronoi diagram for a given point set S of size n, this also enables nearest-neighbor queries in guaranteed O(log n) time. Another major innovation is the support of general unbounded subdivisions as well as subdivisions of two-dimensional parametric surfaces such as spheres, tori, cylinders. The implementation is exact, complete, and general, i.e., it can also handle non-linear subdivisions. Like the previous version, the data structure supports modifications of the subdivision, such as insertions and deletions of edges, after the initial preprocessing. A major challenge is to retain the expected O(n log n) preprocessing time while providing the above (deterministic) space and query-time guarantees. We describe an efficient preprocessing algorithm, which explicitly verifies the length L of the longest query path in O(n log n) time. However, instead of using L, our implementation is based on the depth D of G. Although we prove that the worst case ratio of D and L is Theta(n/log n), we conjecture, based on our experimental results, that this solution achieves expected O(n log n) preprocessing time.
Recommendations
- A new point-location algorithm and its practical efficiency: comparison with existing algorithms
- An experimental study of point location in planar arrangements in CGAL
- Optimal Point Location in a Monotone Subdivision
- Adaptive point location in planar convex subdivisions
- Adaptive Point Location in Planar Convex Subdivisions
Cited in
(8)- Optimal randomized incremental construction for guaranteed logarithmic planar point location
- Improved Grid Map Layout by Point Set Matching
- Point Location in Incremental Planar Subdivisions.
- Adaptive Point Location in Planar Convex Subdivisions
- An experimental study of point location in planar arrangements in CGAL
- Optimal window queries on line segments using the trapezoidal search DAG
- A novel approximation algorithm for max-covering circle problem
- Approximation algorithms for finding maximum containing circle and sphere
This page was built for publication: Improved implementation of point location in general two-dimensional subdivisions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912879)
