{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T05:21:26Z","timestamp":1672377686562},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["236\/06"]},{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","award":["IST-006413"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,2]]},"abstract":"\n We study the performance in practice of various point-location algorithms implemented in CGAL (the Computational Geometry Algorithms Library), including a newly devised\n landmarks<\/jats:italic>\n algorithm. Among the other algorithms studied are: a na\u00efve approach, a \u201cwalk along a line\u201d 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, \u201clandmarks,\u201d 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 \u201cwalk\u201d 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.\n <\/jats:p>","DOI":"10.1145\/1412228.1412237","type":"journal-article","created":{"date-parts":[[2008,10,7]],"date-time":"2008-10-07T12:48:29Z","timestamp":1223383709000},"source":"Crossref","is-referenced-by-count":5,"title":["An experimental study of point location in planar arrangements in CGAL"],"prefix":"10.1145","volume":"13","author":[{"given":"Idit","family":"Haran","sequence":"first","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}]},{"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}]}],"member":"320","published-online":{"date-parts":[[2009,2,23]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"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. 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."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms. 271--280","author":"Arya S."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms. 256--261","author":"Arya S."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms. 262--268","author":"Arya S."},{"key":"e_1_2_1_6_1","unstructured":"Austern M. H. 1999. Generic Programming and the STL. Addison-Wesley Reading MA. Austern M. H. 1999. Generic Programming and the STL. Addison-Wesley Reading MA."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00054-2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/261226"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054102001035"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021819590100064X"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054102001047"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009234"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.02.002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205015"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/357337.357338"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215023"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384255"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 12th Annual European Symposium on Algorithms (ESA). LNCS","volume":"3221","author":"Fogel E."},{"key":"e_1_2_1_20_1","unstructured":"Gamma E. Helm R. Johnson R. and Vlissides J. 1995. Design Patterns\u2014Elements of Reusable Object-Oriented Software. Addison-Wesley Reading MA. Gamma E. Helm R. Johnson R. and Vlissides J. 1995. Design Patterns\u2014Elements of Reusable Object-Oriented Software. Addison-Wesley Reading MA."},{"key":"e_1_2_1_21_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Halperin D.","edition":"2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304989"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"LaValle S. M. 2006. Planning Algorithms. Cambridge University Press Cambridge. Also available at http:\/\/msl.cs.uiuc.edu\/planning\/). LaValle S. M. 2006. Planning Algorithms. Cambridge University Press Cambridge. Also available at http:\/\/msl.cs.uiuc.edu\/planning\/).","DOI":"10.1017\/CBO9780511546877"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek J. 1999. Geometric Discrepancy\u2014An Illustrated Guide. Springer New York Matou\u0161ek J. 1999. Geometric Discrepancy\u2014An Illustrated Guide. Springer New York","DOI":"10.1007\/978-3-642-03942-3"},{"key":"e_1_2_1_26_1","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"Mehlhorn K.","year":"2000"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/237218.237396"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80064-8"},{"key":"e_1_2_1_29_1","first-page":"451","article-title":"A new and useful template technique: \u201cTraits","volume":"5","author":"Myers N.","year":"1997","journal-title":". In C++ Gems, S. B. Lippman, Ed. SIGS Reference Library"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/130653"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210035"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/6138.6151"},{"key":"e_1_2_1_33_1","volume-title":"Handbook of Computational Geometry, J.-R","author":"Schirra S."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(91)90012-4"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803772"},{"key":"e_1_2_1_36_1","unstructured":"Sharir M. and Agarwal P. K. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press Cambridge. Sharir M. and Agarwal P. K. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press Cambridge."},{"key":"e_1_2_1_37_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Snoeyink J.","edition":"2"},{"key":"e_1_2_1_38_1","unstructured":"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. 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."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.11.007"},{"key":"e_1_2_1_40_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Yap C.","edition":"2"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412228.1412237","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T08:56:48Z","timestamp":1672304208000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412228.1412237"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":40,"alternative-id":["10.1145\/1412228.1412237"],"URL":"http:\/\/dx.doi.org\/10.1145\/1412228.1412237","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[2009,2]]}}}