Idit Haran
Abstract
We study the performance in practice of various point-location algorithms implemented in CGAL (the Computational Geometry Algorithms Library), including a newly devised landmarks algorithm. Among the other algorithms studied are: a naïve approach, a “walk along a line” strategy, and a trapezoidal decomposition-based search structure. The current implementation addresses general arrangements of planar curves, including arrangements of nonlinear segments (e.g., conic arcs) and allows for degenerate input (for example, more than two curves intersecting in a single point or overlapping curves). The algorithms use exact geometric computation and thus result in the correct point location. In our landmarks algorithm (a.k.a. jump & walk), special points, “landmarks,” are chosen in a preprocessing stage, their place in the arrangement is found, and they are inserted into a data structure that enables efficient nearest-neighbor search. Given a query point, the nearest landmark is located and a “walk” strategy is applied from the landmark to the query point. We report on various experiments with arrangements composed of line segments or conic arcs. The results indicate that compared to the other algorithms tested, the landmarks approach is the most efficient, when the overall (amortized) cost of a query is taken into account, combining both preprocessing and query time. The simplicity of the algorithm enables an almost straightforward implementation and rather easy maintenance. The generic programming implementation allows versatility both in the selected type of landmarks and in the choice of the nearest-neighbor search structure. The end result is an efficient point-location algorithm that bypasses the alternative CGAL implementations in most practical aspects.
- Agarwal, P. K. and Sharir, M. 2000. Arrangements and their applications. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publi. North-Holland, Amsterdam. 49--119.Google Scholar
- Arya, S. and Mount, D. M. 1993. Approximate nearest neighbor queries in fixed dimensions. In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms. 271--280. Google ScholarDigital Library
- Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., and Wu, A. 1998. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. J. ACM 45, 891--923. Google ScholarDigital Library
- Arya, S., Malamatos, T., and Mount, D. M. 2001a. Entropy-preserving cutting and space-efficient planar point location. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms. 256--261. Google ScholarDigital Library
- Arya, S., Malamatos, T., and Mount, D. M. 2001b. A simple entropy-based algorithm for planar point location. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms. 262--268. Google ScholarDigital Library
- Austern, M. H. 1999. Generic Programming and the STL. Addison-Wesley, Reading, MA.Google Scholar
- Bentley, J. L. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (Sept.), 509--517. Google ScholarDigital Library
- Boissonnat, J.-D., Devillers, O., Pion, S., Teillaud, M., and Yvinec, M. 2002. Triangulations in CGAL. Comput. Geom. Theory Appl. 22, 1--3, 5--19. Google ScholarDigital Library
- de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. 2000. Computational Geometry: Algorithms and Applications, 2nd ed. Springer-Verlag, New York. Google ScholarCross Ref
- Devillers, O. 2002. The Delaunay hierarchy. Intern. J. Found. Comput. Sci. 13, 163--180.Google ScholarCross Ref
- Devillers, O. and Guigue, P. 2001. The shuffling buffer. Intern. J. Comput. Geom. Appl. 11, 555--572.Google ScholarCross Ref
- Devillers, O., Pion, S., and Teillaud, M. 2002. Walking in a triangulation. Intern. J. Found. Comput. Sci. 13, 181--199.Google ScholarCross Ref
- Devroye, L., Mücke, E. P., and Zhu, B. 1998. A note on point location in Delaunay triangulations of random points. Algorithmica 22, 477--482.Google ScholarCross Ref
- Devroye, L., Lemaire, C., and Moreau, J.-M. 2004. Expected time analysis for Delaunay point location. Comput. Geom. Theory Appl. 29, 2, 61--89. Google ScholarDigital Library
- Dobkin, D. P. and Lipton, R. J. 1976. Multidimensional searching problems. SIAM J. Comput. 5, 2, 181--186.Google ScholarDigital Library
- Edahiro, M., Kokubo, I., and Asano, T. 1984. A new point-location algorithm and its practical efficiency—comparison with existing algorithms. ACM Trans. Graph. 3, 86--109. Google ScholarDigital Library
- Edelsbrunner, H., Guibas, L. J., and Stolfi, J. 1986. Optimal point location in a monotone subdivision. SIAM J. Comput. 15, 2, 317--340. Google ScholarDigital Library
- Flato, E., Halperin, D., Hanniel, I., Nechushtan, O., and Ezra, E. 2000. The design and implementation of planar maps in CGAL. ACM J. Exp. Algorithmics 5. Special Issue, selected papers of the Workshop on Algorithm Engineering (WAE). Google ScholarDigital Library
- Fogel, E., Wein, R., and Halperin, D. 2004. Code flexibility and program efficiency by genericity: Improving CGAL's arrangements. In Proceedings of the 12th Annual European Symposium on Algorithms (ESA). LNCS, vol. 3221. Springer-Verlag, New York. 664--676.Google Scholar
- Gamma, E., Helm, R., Johnson, R., and Vlissides, J. 1995. Design Patterns—Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading, MA. Google ScholarDigital Library
- Halperin, D. 2004. Arrangements. In Handbook of Discrete and Computational Geometry, 2nd ed., J. E. Goodman and J. O'Rourke, Eds. Chapman & Hall/CRC, Boca Raton, FL. 529--562.Google Scholar
- Karamcheti, V., Li, C., Pechtchanski, I., and Yap, C. 1999. A Core library for robust numeric and geometric computation. In Proceedings of the 15th Annual Symposium on Computational Geometry. 351--359. Google ScholarDigital Library
- Kirkpatrick, D. G. 1983. Optimal search in planar subdivisions. SIAM J. Comput. 12, 1, 28--35.Google ScholarDigital Library
- LaValle, S. M. 2006. Planning Algorithms. Cambridge University Press Cambridge. Also available at http://msl.cs.uiuc.edu/planning/). Google ScholarDigital Library
- Matoušek, J. 1999. Geometric Discrepancy—An Illustrated Guide. Springer, New YorkGoogle Scholar
- Mehlhorn, K. and Näher, S. 2000. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge, UK. Google ScholarDigital Library
- Mücke, E. P., Saias, I., and Zhu, B. 1996. Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations. In Proceedings of the 12th Annual ACM Symposium on Computational Geometry. 274--283. Google ScholarDigital Library
- Mulmuley, K. 1990. A fast planar partition algorithm, I. J. Symbolic Comput. 10, 3-4, 253--280. Google ScholarDigital Library
- Myers, N. 1997. A new and useful template technique: “Traits”. In C++ Gems, S. B. Lippman, Ed. SIGS Reference Library, vol. 5. 451--458. Google ScholarDigital Library
- Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. Regional Conference Series in Applied Mathematics, vol. 63. CBMS-NSF. Google ScholarDigital Library
- Preparata, F. P. 1981. A new approach to planar point location. SIAM J. Comput. 10, 3, 473--482.Google ScholarDigital Library
- Sarnak, N. and Tarjan, R. E. 1986. Planar point location using persistent search trees. Commun. ACM 29, 7 (July), 669--679. Google ScholarDigital Library
- Schirra, S. 2000. Robustness and precision issues in geometric computation. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publ. North-Holland, Amsterdam. 597--632.Google Scholar
- Seidel, R. 1991. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl. 1, 1, 51--64. Google ScholarDigital Library
- Shamos, M. I. 1975. Geometric complexity. In Proceedings of the 7th ACM Symposium on Theory of Computing. 224--233. Google ScholarDigital Library
- Sharir, M. and Agarwal, P. K. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge. Google ScholarDigital Library
- Snoeyink, J. 2004. Point location. In Handbook of Discrete and Computational Geometry, 2nd ed., J. E. Goodman and J. O'Rourke, Eds. Chapman & Hall/CRC, Boca Raton. Chapter 34, 529--562. Google ScholarDigital Library
- Tangelder, H. and Fabri, A. 2006. dD spatial searching. In Cgal-3.2 User and Reference Manual, Cgal Editorial Board, Ed. http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Spatial_searching/Chapter_main.html.Google Scholar
- Wein, R., Fogel, E., Zukerman, B., and Halperin, D. 2007. Advanced programming techniques applied to CGAL's arrangement package. Comput. Geom. Theory Appl. 38, 1-2, 37--63. Google ScholarDigital Library
- Yap, C. 2004. Robust geometric computation. In Handbook of Discrete and Computational Geometry, 2nd ed., J. E. Goodman and J. O'Rourke, Eds. Chapman & Hall/CRC, Boca Raton, FL. 927--952. Google ScholarDigital Library
Index Terms
- An experimental study of point location in planar arrangements in CGAL
Recommendations
Advanced programming techniques applied to Cgal's arrangement package
Arrangements of planar curves are fundamental structures in computational geometry. Recently, the arrangement package of Cgal, the Computational Geometry Algorithms Library, has been redesigned and re-implemented exploiting several advanced programming ...
Constructing the exact Voronoi diagram of arbitrary lines in three-dimensional space with fast point-location
ESA'10: Proceedings of the 18th annual European conference on Algorithms: Part IWe introduce a new, efficient, and complete algorithm, and its exact implementation, to compute the Voronoi diagram of lines in space. This is a major milestone towards the robust construction of the Voronoi diagram of polyhedra. As we follow the exact ...
An exact, complete and efficient computation of arrangements of Bézier curves
SPM '07: Proceedings of the 2007 ACM symposium on Solid and physical modelingArrangements of planar curves are fundamental structures in computational geometry. The arrangement package of CGAL can construct and maintain arrangements of various families of curves, when provided with the representation of the curves and some basic ...
Comments