×

Optimal randomized incremental construction for guaranteed logarithmic planar point location. (English) Zbl 1357.65023

The paper deals with one of the fundamental problems in computational geometry, namely with the planar point location. The authors revisit the randomized incremental construction of the trapezoidal map and the related search structures. At the beginning the authors describe the basic random incremental construction in which a trapezoidal map \(T\) is constructed and a directed acyclic graph \(G\) is maintained during the incremental construction. Moreover, some discussion on guaranteeing the logarithmic query time is made. Next, the authors study the depth \(D\) of \(G\) and the longest search path \(L\) in \(G\). They prove that the worst-case ratio between \(D\) and \(L\) can be \(\Theta(n / \log n)\), where \(n\) is the number of pairwise interior disjoint \(x\)-monotone curves inducing the planar subdivision. Later, they prove that there exists a bijection among all search paths in \(G\) and those in \(T\). Using these results the authors propose an algorithm for the construction of a trapezoidal map that has an expected \(O(n \log n)\) preprocessing time, an expected \(O(\log n)\) query time and requires an expected \(O(n)\) space.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

CGAL
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Arya, S.; Malamatos, T.; Mount, D. M., Entropy-preserving cuttings and space-efficient planar point location, (Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2001)), 256-261 · Zbl 0987.68082
[2] Arya, S.; Malamatos, T.; Mount, D. M., A simple entropy-based algorithm for planar point location, (Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2001)), 262-268 · Zbl 0987.68083
[3] de Berg, M.; van Kreveld, M.; Overmars, M.; Schwarzkopf, O., Computational Geometry: Algorithms and Applications (2008), Springer
[4] Devillers, O., The Delaunay hierarchy, Int. J. Found. Comput. Sci., 13, 2, 163-180 (2002) · Zbl 1066.68138
[5] Dobkin, D. P.; Lipton, R. J., Multidimensional searching problems, SIAM J. Comput., 5, 2, 181-186 (1976) · Zbl 0333.68031
[6] Edelsbrunner, H.; Guibas, L. J.; Stolfi, J., Optimal point location in a monotone subdivision, SIAM J. Comput., 15, 2, 317-340 (1986) · Zbl 0602.68102
[7] Flato, E.; Halperin, D.; Hanniel, I.; Nechushtan, O.; Ezra, E., The design and implementation of planar maps in CGAL, ACM J. Exp. Algorithmics, 5, 13 (2000) · Zbl 1071.68556
[8] Fogel, E.; Halperin, D.; Wein, R., CGAL Arrangements and Their Applications (2012), Springer · Zbl 1258.65025
[9] Har-Peled, S., Constructing planar cuttings in theory and practice, SIAM J. Comput., 29, 6, 2016-2039 (2000) · Zbl 0981.65027
[10] Hemmer, M.; Kleinbort, M.; Halperin, D., Improved implementation of point location in general two-dimensional subdivisions, (Proceedings of the 20th Annual European Symposium on Algorithms (ESA) (2012)), 611-623 · Zbl 1365.68444
[11] Hemmer, M.; Kleinbort, M.; Halperin, D., Optimal randomized incremental construction for guaranteed logarithmic planar point location, CoRR · Zbl 1357.65023
[12] Kirkpatrick, D. G., Optimal search in planar subdivisions, SIAM J. Comput., 12, 1, 28-35 (1983) · Zbl 0501.68034
[13] Kleinbort, M., Guaranteed logarithmic-time point location in general two-dimensional subdivisions (2013), Blavatnik School of Computer Science, Tel Aviv University: Blavatnik School of Computer Science, Tel Aviv University Israel, M.Sc. thesis
[14] Lee, D. T.; Preparata, F. P., Location of a point in a planar subdivision and its applications, SIAM J. Comput., 6, 3, 594-606 (1977) · Zbl 0357.68034
[15] Mulmuley, K., A fast planar partition algorithm, I, J. Symb. Comput., 10, 3/4, 253-280 (1990) · Zbl 0717.68104
[16] Mulmuley, K., Computational Geometry - An Introduction Through Randomized Algorithms (1994), Prentice Hall
[17] Preparata, F. P., A new approach to planar point location, SIAM J. Comput., 10, 3, 473-482 (1981) · Zbl 0462.68048
[18] Sarnak, N.; Tarjan, R. E., Planar point location using persistent search trees, Commun. ACM, 29, 7, 669-679 (1986)
[19] Seidel, R., A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Comput. Geom.: Theory Appl., 1, 51-64 (1991) · Zbl 0733.68092
[20] Seidel, R.; Adamy, U., On the exact worst case query complexity of planar point location, J. Algorithms, 37, 1, 189-217 (2000) · Zbl 0971.68072
[21] Snoeyink, J., Point location, (Goodman, J. E.; O’Rourke, J., Handbook of Discrete and Computational Geometry (2004), Chapman & Hall/CRC), 767-785, Chap. 34
[22] Snoeyink, J.; van Kreveld, M., Good orders for incremental (re)construction, (Proceedings of the Thirteenth Annual Symposium on Computational Geometry. Proceedings of the Thirteenth Annual Symposium on Computational Geometry, SCG ’97 (1997), ACM), 400-402
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.