×

Practical distribution-sensitive point location in triangulations. (English) Zbl 1283.65014

Summary: We design, analyze, implement, and evaluate a distribution-sensitive point location algorithm based on the classical jump & walk, called keep, jump, & walk. For a batch of query points, the main idea is to use previous queries to improve the current one. In practice, keep, jump, & walk is actually a very competitive method to locate points in a triangulation. We also study some constant-memory distribution-sensitive point location algorithms, which work well in practice with the classical space-filling heuristic for fast point location. Regarding point location in a Delaunay triangulation, we show how the Delaunay hierarchy can be used to answer, under some hypotheses, a query \(q\) with an \(O(\log\sharp(pq))\) randomized expected complexity, where \(p\) is a previously located query and \(\sharp(s)\) indicates the number of simplices crossed by the line segment \(s\). The Delaunay hierarchy has \(O(n\log n)\) time complexity and \(O(n)\) memory complexity in the plane, and under certain realistic hypotheses these complexities generalize to any finite dimension. Finally, we combine the good distribution-sensitive behavior of keep, jump, & walk, and the good complexity of the Delaunay hierarchy, into a novel point location algorithm called keep, jump, & climb. To the best of our knowledge, keep, jump, & climb is the first practical distribution-sensitive algorithm that works both in theory and in practice for Delaunay triangulations.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Arya, S.; Malamatos, T.; Mount, D. M., A simple entropy-based algorithm for planar point location, ACM Trans. Algorithms, 3, 2, 1-17 (2007) · Zbl 1321.68429
[4] Attali, D.; Boissonnat, J.-Daniel, A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces, Discrete Comput. Geom., 31, 369-384 (2004) · Zbl 1063.68100
[5] Beardwood, J.; Halton, J. H.; Hammersley, J. M., The shortest path through many points, Math. Proc. Camb. Phil. Soc., 55, 299-327 (1959) · Zbl 0118.35601
[6] Bose, P.; Devroye, L., On the stabbing number of a random Delaunay triangulation, Comput. Geom. Theory Appl., 36, 2, 89-105 (2007) · Zbl 1105.65020
[7] Bowyer, A., Computing Dirichlet tessellations, Comput. J., 24, 162-166 (1981)
[10] Chazelle, B.; Liu, D.; Magen, A., Sublinear geometric algorithms, SIAM J. Comput., 35, 627-646 (2006) · Zbl 1095.68124
[11] Core number library
[12] de Castro, P. M.M.; Devillers, O., On the asymptotic growth rate of some spanning trees embedded in \(R^d\), Operations Research Letters, 39, 1, 44-48 (2011) · Zbl 1211.90267
[15] Demaine, Erik D.; Iacono, John; Langerman, Stefan, Proximate point searching, Comput. Geom. Theory Appl., 28, 1, 29-40 (2004) · Zbl 1140.68509
[16] Demaine, E. D.; Mitchell, J. S.B.; OʼRourke, J., The Open Problems Project
[17] Devillers, O., The Delaunay hierarchy, Internat. J. Found. Comput. Sci., 13, 163-180 (2002) · Zbl 1066.68138
[18] Devillers, O.; Pion, Sylvain; Teillaud, Monique, Walking in a triangulation, Internat. J. Found. Comput. Sci., 13, 181-199 (2002) · Zbl 1066.68139
[19] Devroye, L.; Mücke, E. P.; Zhu, B., A note on point location in Delaunay triangulations of random points, Algorithmica, 22, 477-482 (1998) · Zbl 0914.68201
[20] Devroye, L.; Lemaire, C.; Moreau, J.-M., Expected time analysis for Delaunay point location, Comput. Geom. Theory Appl., 29, 61-89 (2004) · Zbl 1064.65018
[21] Dwyer, R., Convex hulls of samples from spherically symmetric distributions, Discrete Appl. Math., 31, 2, 113-132 (1991) · Zbl 0736.52007
[23] Gao, J.; Steele, J. M., General spacefilling curve heuristics and limit theory for the traveling salesman problem, J. Complexity, 10, 230-245 (1994) · Zbl 0820.90115
[24] Golin, M. J.; Na, H.-S., On the average complexity of 3d-Voronoi diagrams of random points on convex polytopes, Comput. Geom. Theory Appl., 25, 197-231 (2003) · Zbl 1023.65014
[25] (Goodman, J. E.; OʼRourke, J., Handbook of Discrete and Computational Geometry (2004), CRC Press LLC: CRC Press LLC Boca Raton, FL)
[26] Green, P. J.; Sibson, R. R., Computing Dirichlet tessellations in the plane, Comput. J., 21, 168-173 (1978) · Zbl 0377.52001
[27] Haran, I.; Halperin, D., An experimental study of point location in planar arrangements in CGAL, J. Exp. Algorithmics, 13, 2.3-2.32 (2009) · Zbl 1284.68634
[28] Iacono, J., Improved upper bounds for pairing heaps, (Proc. 7th Scandinavian Workshop on Algorithm Theory (2000), Springer-Verlag: Springer-Verlag London, UK), 32-45 · Zbl 0966.68509
[29] Iacono, J., Expected asymptotically optimal planar point location, Comput. Geom. Theory Appl., 29, 1, 19-22 (2004) · Zbl 1057.65008
[32] Kazhdan, M.; Bolitho, M.; Hoppe, H., Poisson surface reconstruction, (Proc. 4th Eurographics Symp. on Geom. Processing (2006), Eurographics Association: Eurographics Association Aire-la-Ville, Switzerland), 61-70
[33] Kettner, L.; Mehlhorn, K.; Pion, S.; Schirra, S.; Yap, C., Classroom examples of robustness problems in geometric computations, (Proc. 12th European Symp. on Algorithms. Proc. 12th European Symp. on Algorithms, Lecture Notes Comput. Sci., vol. 3221 (2004), Springer-Verlag), 702-713 · Zbl 1111.68725
[34] Kirkpatrick, D. G., Optimal search in planar subdivisions, SIAM J. Comput., 12, 1, 28-35 (1983) · Zbl 0501.68034
[35] Knuth, D. E., Optimum binary search trees, Acta Inf., 1, 14-25 (1971) · Zbl 0233.68010
[36] Leda, Library for efficient data types and algorithms
[37] Malamatos, T., Lower bounds for expected-case planar point location, Comput. Geom. Theory Appl., 39, 2, 91-103 (2008) · Zbl 1128.65021
[40] Platzman, L. K.; Bartholdi, J. J., III. Spacefilling curves and the planar travelling salesman problem, J. ACM, 36, 4, 719-737 (October 1989)
[41] Santaló, L. A., Integral Geometry and Geometric Probability (1976), Addison-Wesley · Zbl 0342.53049
[42] Shewchuk, J. R., Stabbing Delaunay tetrahedralizations, Discrete Comput. Geom., 32, 343 (2002) · Zbl 1092.52007
[43] Skiena, Steven S., The Algorithm Design Manual (2008), Springer · Zbl 1149.68081
[44] Steele, J. M., Cost of sequential connection for points in space, Oper. Res. Lett., 8, 137-142 (1989) · Zbl 0675.90084
[45] Steele, J. M.; Snyder, T. L., Worst-case growth rates of some classical problems of combinatorial optimization, SIAM J. Comput., 18, 278-287 (1989) · Zbl 0674.90080
[46] The Gnu multiple precision arithmetic library
[47] Yap, C. K.; Dubé, T., The exact computation paradigm, (Du, D.-Z.; Hwang, F. K., Computing in Euclidean Geometry. Computing in Euclidean Geometry, Lecture Notes Ser. Comput., vol. 4 (1995), World Scientific: World Scientific Singapore), 452-492
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.