{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:24:32Z","timestamp":1760441072478},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_53","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"611-623","source":"Crossref","is-referenced-by-count":6,"title":["Improved Implementation of Point Location in General Two-Dimensional Subdivisions"],"prefix":"10.1007","author":[{"given":"Michael","family":"Hemmer","sequence":"first","affiliation":[]},{"given":"Michal","family":"Kleinbort","sequence":"additional","affiliation":[]},{"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"53_CR1","doi-asserted-by":"crossref","unstructured":"Birn, M., Holtgrewe, M., Sanders, P., Singler, J.: Simple and fast nearest neighbor search. In: Workshop on Algorithm Engineering and Experiments, pp. 43\u201354 (2010)","DOI":"10.1137\/1.9781611972900.5"},{"issue":"3\/4","key":"53_CR2","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0747-7171(08)80064-8","volume":"10","author":"K. Mulmuley","year":"1990","unstructured":"Mulmuley, K.: A fast planar partition algorithm. i. J. Symb. Comput.\u00a010(3\/4), 253\u2013280 (1990)","journal-title":"i. J. Symb. Comput."},{"key":"53_CR3","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0925-7721(91)90012-4","volume":"1","author":"R. Seidel","year":"1991","unstructured":"Seidel, R.: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. J. Comput. Geom.\u00a01, 51\u201364 (1991)","journal-title":"J. Comput. Geom."},{"issue":"1","key":"53_CR4","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D.G. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.G.: Optimal search in planar subdivisions. SIAM J. Comput.\u00a012(1), 28\u201335 (1983)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"53_CR5","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1142\/S0129054102001035","volume":"13","author":"O. Devillers","year":"2002","unstructured":"Devillers, O.: The Delaunay hierarchy. Int. J. Found. Comput. Sci.\u00a013(2), 163\u2013180 (2002)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"53_CR6","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1006\/jagm.2000.1101","volume":"37","author":"R. Seidel","year":"2000","unstructured":"Seidel, R., Adamy, U.: On the exact worst case query complexity of planar point location. J. Algorithms\u00a037(1), 189\u2013217 (2000)","journal-title":"J. Algorithms"},{"issue":"2","key":"53_CR7","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"D.P. Dobkin","year":"1976","unstructured":"Dobkin, D.P., Lipton, R.J.: Multidimensional searching problems. SIAM J. Comput.\u00a05(2), 181\u2013186 (1976)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"53_CR8","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1137\/0210035","volume":"10","author":"F.P. Preparata","year":"1981","unstructured":"Preparata, F.P.: A new approach to planar point location. SIAM J. Comput.\u00a010(3), 473\u2013482 (1981)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"53_CR9","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. Commun. ACM\u00a029(7), 669\u2013679 (1986)","journal-title":"Commun. ACM"},{"key":"53_CR10","series-title":"STOC 1976","first-page":"231","volume-title":"ACM Symposium on Theory of Computing","author":"D.T. Lee","year":"1976","unstructured":"Lee, D.T., Preparata, F.P.: Location of a point in a planar subdivision and its applications. In: ACM Symposium on Theory of Computing. STOC 1976, pp. 231\u2013235. ACM, New York (1976)"},{"issue":"2","key":"53_CR11","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput.\u00a015(2), 317\u2013340 (1986)","journal-title":"SIAM J. Comput."},{"key":"53_CR12","first-page":"767","volume-title":"Handbook of Discrete and Computational Geometry","author":"J. Snoeyink","year":"2004","unstructured":"Snoeyink, J.: Point location. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 767\u2013785. CRC Press LLC, Boca Raton (2004)"},{"key":"53_CR13","doi-asserted-by":"crossref","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer (2008)","DOI":"10.1007\/978-3-540-77974-2"},{"key":"53_CR14","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s11786-010-0043-4","volume":"4","author":"E. Berberich","year":"2010","unstructured":"Berberich, E., Fogel, E., Halperin, D., Melhorn, K., Wein, R.: Arrangements on parametric surfaces I: General framework and infrastructure. Mathematics in Computer Science\u00a04, 67\u201391 (2010)","journal-title":"Mathematics in Computer Science"},{"key":"53_CR15","unstructured":"Mulmuley, K.: Computational geometry - an introduction through randomized algorithms. Prentice Hall (1994)"},{"key":"53_CR16","doi-asserted-by":"crossref","unstructured":"Hemmer, M., Kleinbort, M., Halperin, D.: Improved implementation of point location in general two-dimensional subdivisions. CoRR abs\/1205.5434 (2012)","DOI":"10.1007\/978-3-642-33090-2_53"},{"key":"53_CR17","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Yao, F.F.: On translating a set of rectangles. In: STOC, pp. 154\u2013160 (1980)","DOI":"10.1145\/800141.804663"},{"key":"53_CR18","unstructured":"Alt, H., Scharf, L.: Computing the depth of an arrangement of axis-aligned rectangles in parallel. In: Proceedings of the 26th European Workshop on Computational Geometry (EuroCG), Dortmund, Germany, pp. 33\u201336 (March 2010)"},{"key":"53_CR19","doi-asserted-by":"crossref","unstructured":"Amenta, N., Choi, S., Rote, G.: Incremental constructions con brio. In: Symposium on Computational Geometry, pp. 211\u2013219 (2003)","DOI":"10.1145\/777792.777824"},{"key":"53_CR20","unstructured":"Mount, D.M., Arya, S.: Ann: A library for approximate nearest neighbor searching, \n                  \n                    http:\/\/www.cs.umd.edu\/~mount\/ANN\/"},{"key":"53_CR21","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/351827.384255","volume":"5","author":"E. Flato","year":"2000","unstructured":"Flato, E., Halperin, D., Hanniel, I., Nechushtan, O., Ezra, E.: The design and implementation of planar maps in CGAL. ACM Journal of Experimental Algorithmics\u00a05, 13 (2000)","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"53_CR22","unstructured":"Wein, R., Berberich, E., Fogel, E., Halperin, D., Hemmer, M., Salzman, O., Zukerman, B.: 2D arrangements. In: CGAL User and Reference Manual, 4.0 edn., CGAL Editorial Board (2012)"},{"key":"53_CR23","unstructured":"Austern, M.H.: Generic Programming and the STL. Addison-Wesley (1999)"},{"key":"53_CR24","doi-asserted-by":"crossref","unstructured":"Haran, I., Halperin, D.: An experimental study of point location in planar arrangements in CGAL. ACM Journal of Experimental Algorithmics\u00a013 (2008)","DOI":"10.1145\/1412228.1412237"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_53.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:55:02Z","timestamp":1620129302000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}