@inbook {IOPORT.06086357,
    author       = {Hemmer, Michael and Kleinbort, Michal and Halperin, Dan},
    title        = {Improved implementation of point location in general two-dimensional subdivisions.},
    year         = {2012},
    booktitle    = {Algorithms -- ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10--12, 2012. Proceeding},
    isbn         = {978-3-642-33089-6},
    pages        = {611-623},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-33090-2_53},
    abstract     = {Summary: 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(\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 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 $\Theta (n/\log n)$, we conjecture, based on our experimental results, that this solution achieves expected $O(n \log n)$ preprocessing time.},
    identifier   = {06086357},
}