Name
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 $\mathcal 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(logn) 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 logn) preprocessing time while providing the above (deterministic) space and query-time guarantees. We describe efficient preprocessing algorithms, which explicitly verify the length $\mathcal L$ of the longest query path. However, instead of using $\mathcal L$, our implementation is based on the depth $\mathcal D$ of $\mathcal G$. Although we prove that the worst case ratio of $\mathcal D$ and $\mathcal L$ is Θ(n/logn), we conjecture, based on our experimental results, that this solution achieves expected O(n logn) preprocessing time. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-33090-2_53 | european symposium on algorithms |
Keywords | DocType | Volume |
initial preprocessing,general two-dimensional subdivision,expected o,mathcal g,efficient preprocessing algorithm,logarithmic query time,mathcal d,preprocessing time,improved implementation,n logn,point location,mathcal l | Conference | abs/1205.5434 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.40 |
References | Authors | |
19 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Hemmer | 1 | 184 | 15.62 |
| Michal Kleinbort | 2 | 7 | 2.21 |
| Dan Halperin | 3 | 1291 | 105.20 |