research-article

An experimental study of point location in planar arrangements in CGAL

Authors:

Dan HalperinAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 13

Article No.: 3, Pages 2.3 - 2.32

https://doi.org/10.1145/1412228.1412237

Published: 23 February 2009 Publication History

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.

References

[1]

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.

[2]

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.

Digital Library

[3]

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.

Digital Library

[4]

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.

Digital Library

[5]

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.

Digital Library

[6]

Austern, M. H. 1999. Generic Programming and the STL. Addison-Wesley, Reading, MA.

[7]

Bentley, J. L. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (Sept.), 509--517.

Digital Library

[8]

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.

Digital Library

[9]

de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. 2000. Computational Geometry: Algorithms and Applications, 2nd ed. Springer-Verlag, New York.

[10]

Devillers, O. 2002. The Delaunay hierarchy. Intern. J. Found. Comput. Sci. 13, 163--180.

[11]

Devillers, O. and Guigue, P. 2001. The shuffling buffer. Intern. J. Comput. Geom. Appl. 11, 555--572.

[12]

Devillers, O., Pion, S., and Teillaud, M. 2002. Walking in a triangulation. Intern. J. Found. Comput. Sci. 13, 181--199.

[13]

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.

[14]

Devroye, L., Lemaire, C., and Moreau, J.-M. 2004. Expected time analysis for Delaunay point location. Comput. Geom. Theory Appl. 29, 2, 61--89.

Digital Library

[15]

Dobkin, D. P. and Lipton, R. J. 1976. Multidimensional searching problems. SIAM J. Comput. 5, 2, 181--186.

Digital Library

[16]

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.

Digital Library

[17]

Edelsbrunner, H., Guibas, L. J., and Stolfi, J. 1986. Optimal point location in a monotone subdivision. SIAM J. Comput. 15, 2, 317--340.

Digital Library

[18]

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).

Digital Library

[19]

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.

[20]

Gamma, E., Helm, R., Johnson, R., and Vlissides, J. 1995. Design Patterns—Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading, MA.

Digital Library

[21]

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.

[22]

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.

Digital Library

[23]

Kirkpatrick, D. G. 1983. Optimal search in planar subdivisions. SIAM J. Comput. 12, 1, 28--35.

Digital Library

[24]

LaValle, S. M. 2006. Planning Algorithms. Cambridge University Press Cambridge. Also available at http://msl.cs.uiuc.edu/planning/).

Digital Library

[25]

Matoušek, J. 1999. Geometric Discrepancy—An Illustrated Guide. Springer, New York

[26]

Mehlhorn, K. and Näher, S. 2000. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge, UK.

Digital Library

[27]

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.

Digital Library

[28]

Mulmuley, K. 1990. A fast planar partition algorithm, I. J. Symbolic Comput. 10, 3-4, 253--280.

Digital Library

[29]

Myers, N. 1997. A new and useful template technique: “Traits”. In C++ Gems, S. B. Lippman, Ed. SIGS Reference Library, vol. 5. 451--458.

Digital Library

[30]

Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. Regional Conference Series in Applied Mathematics, vol. 63. CBMS-NSF.

Digital Library

[31]

Preparata, F. P. 1981. A new approach to planar point location. SIAM J. Comput. 10, 3, 473--482.

Digital Library

[32]

Sarnak, N. and Tarjan, R. E. 1986. Planar point location using persistent search trees. Commun. ACM 29, 7 (July), 669--679.

Digital Library

[33]

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.

[34]

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.

Digital Library

[35]

Shamos, M. I. 1975. Geometric complexity. In Proceedings of the 7th ACM Symposium on Theory of Computing. 224--233.

Digital Library

[36]

Sharir, M. and Agarwal, P. K. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge.

Digital Library

[37]

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.

Digital Library

[38]

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.

[39]

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.

Digital Library

[40]

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.

Digital Library

Cited By

Roeloffzen M(2016)Point LocationEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_587(1585-1589)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_587
Roeloffzen M(2015)Point LocationEncyclopedia of Algorithms10.1007/978-3-642-27848-8_587-1(1-5)Online publication date: 10-Feb-2015
https://doi.org/10.1007/978-3-642-27848-8_587-1
de Castro PDevillers O(2013)Practical distribution-sensitive point location in triangulationsComputer Aided Geometric Design10.1016/j.cagd.2013.02.00430:5(431-450)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1016/j.cagd.2013.02.004
Show More Cited By

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 I

We 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 modeling

Arrangements 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

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 13, Issue

2009

482 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/1412228

Issue’s Table of Contents

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 February 2009

Accepted: 01 May 2008

Revised: 01 March 2007

Received: 01 June 2006

Published in JEA Volume 13

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
443
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Roeloffzen M(2016)Point LocationEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_587(1585-1589)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_587
Roeloffzen M(2015)Point LocationEncyclopedia of Algorithms10.1007/978-3-642-27848-8_587-1(1-5)Online publication date: 10-Feb-2015
https://doi.org/10.1007/978-3-642-27848-8_587-1
de Castro PDevillers O(2013)Practical distribution-sensitive point location in triangulationsComputer Aided Geometric Design10.1016/j.cagd.2013.02.00430:5(431-450)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1016/j.cagd.2013.02.004
Hemmer MKleinbort MHalperin D(2012)Improved implementation of point location in general two-dimensional subdivisionsProceedings of the 20th Annual European conference on Algorithms10.1007/978-3-642-33090-2_53(611-623)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-33090-2_53
Hemmer MSetter OHalperin D(2010)Constructing the exact Voronoi diagram of arbitrary lines in three-dimensional space with fast point-locationProceedings of the 18th annual European conference on Algorithms: Part I10.5555/1888935.1888980(398-409)Online publication date: 6-Sep-2010
https://dl.acm.org/doi/10.5555/1888935.1888980
Hemmer MSetter OHalperin D(2010)Constructing the Exact Voronoi Diagram of Arbitrary Lines in Three-Dimensional SpaceAlgorithms – ESA 201010.1007/978-3-642-15775-2_34(398-409)Online publication date: 2010
https://doi.org/10.1007/978-3-642-15775-2_34

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents