An experimental study of point location in planar arrangements in CGAL

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An experimental study of point location in planar arrangements in CGAL

Full text

Pdf (1.56 MB)

Source

Journal of Experimental Algorithmics (JEA) archive
Volume 13 , (February 2009) table of contents

SECTION: SECTION: 2 - Selected Papers from ALENEX 2006 table of contents

Article No. 3

Year of Publication: 2009

ISSN:1084-6654

Authors

Idit Haran	Tel-Aviv University, Tel-Aviv, Israel
Dan Halperin	Tel-Aviv University, Tel-Aviv, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 114, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1412228.1412237 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.
	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.
	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.
	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.
	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.
	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.
	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.
	15	Dobkin, D. P. and Lipton, R. J. 1976. Multidimensional searching problems. SIAM J. Comput. 5, 2, 181--186.
	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.
	17	Edelsbrunner, H., Guibas, L. J., and Stolfi, J. 1986. Optimal point location in a monotone subdivision. SIAM J. Comput. 15, 2, 317--340.
	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).
	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.
	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.
	23	Kirkpatrick, D. G. 1983. Optimal search in planar subdivisions. SIAM J. Comput. 12, 1, 28--35.
	24	LaValle, S. M. 2006. Planning Algorithms. Cambridge University Press Cambridge. Also available at http://msl.cs.uiuc.edu/planning/).
	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.
	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.
	28	Mulmuley, K. 1990. A fast planar partition algorithm, I. J. Symbolic Comput. 10, 3-4, 253--280.
	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.
	30	Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. Regional Conference Series in Applied Mathematics, vol. 63. CBMS-NSF.
	31	Preparata, F. P. 1981. A new approach to planar point location. SIAM J. Comput. 10, 3, 473--482.
	32	Sarnak, N. and Tarjan, R. E. 1986. Planar point location using persistent search trees. Commun. ACM 29, 7 (July), 669--679.
	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.
	35	Shamos, M. I. 1975. Geometric complexity. In Proceedings of the 7th ACM Symposium on Theory of Computing. 224--233.
	36	Sharir, M. and Agarwal, P. K. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge.
	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.
	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.
	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.