{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:49:08Z","timestamp":1787496548816,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540505174","type":"print"},{"value":"9783540460305","type":"electronic"}],"license":[{"start":{"date-parts":[[1988,1,1]],"date-time":"1988-01-01T00:00:00Z","timestamp":567993600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-50517-2_67","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:25:36Z","timestamp":1330183536000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Planar point location revisited (A guided tour of a decade of research)"],"prefix":"10.1007","author":[{"given":"Franco P.","family":"Preparata","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B.M. Chazelle","year":"1986","unstructured":"B.M. Chazelle and L.J. Guibas, \u201cFractional cascading: I. A data structuring technique,\u201d Algorithmica, vol. 1, pp. 133\u2013162, 1986.","journal-title":"Algorithmica"},{"issue":"2","key":"1_CR2","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1016\/0196-6774(86)90004-0","volume":"7","author":"R. Cole","year":"1986","unstructured":"R. Cole, \u201cSearching and storing similar list,\u201d Journal of Algorithms, vol. 7, n. 2, pp. 202\u2013220; 1986.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"1_CR3","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"D.P. Dobkin","year":"1976","unstructured":"D.P. Dobkin and R.J. Lipton, \u201cMultidimensional Searching Problems,\u201d SIAM J. Computing vol. 5, no. 2, pp. 181\u2013186, 1976.","journal-title":"SIAM J. Computing"},{"issue":"2","key":"1_CR4","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/357337.357338","volume":"3","author":"M. Edahiro","year":"1984","unstructured":"M. Edahiro, I. Kokubo, and T. Asano, \u201cA New Point-Location Algorithm and its Practical Efficiency \u2014 Comparison with Existing Algorithms,\u201d ACM Trans. on Graphics, vol 3, no. 2, pp. 86\u2013109, 1984.","journal-title":"ACM Trans. on Graphics"},{"issue":"2","key":"1_CR5","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, L.J. Guibas, and J. Stolfi, \u201cOptimal Point Location in a Monotone Subdivision,\u201d SIAM J. Computing, vol. 15, no. 2, pp. 317\u2013340, 1986.","journal-title":"SIAM J. Computing"},{"key":"1_CR6","volume-title":"Zerlegung einer planaren Unterteilung der Ebene und ihre Anwendungen","author":"O. Fries","year":"1985","unstructured":"O. Fries, \u201cZerlegung einer planaren Unterteilung der Ebene und ihre Anwendungen,\u201d M.S. Thesis, Inst. Angew. Math. and Inform., Univ. Saarlandes, Saarbr\u00fccken, Germany, 1985."},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"O. Fries, K. Mehlhorn, and S. N\u00e4her, \u201cDynamization of Geometric Data Structures,\u201d Proc. ACM Symp. on Computational Geometry, pp. 168\u2013176, 1985.","DOI":"10.1145\/323233.323256"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"L.J. Guibas and R. Sedgewick, \u201cA Dichromatic Framework for Balanced Trees,\u201d Proc. 19th IEEE Symp. on Foundations of Computer Science, pp. 8\u201321, 1978.","DOI":"10.1109\/SFCS.1978.3"},{"issue":"1","key":"1_CR9","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D.G. Kirkpatrick","year":"1983","unstructured":"D.G. Kirkpatrick, \u201cOptimal Search in Planar Subdivisions,\u201d SIAM J. Computing, vol. 12, no. 1, pp. 28\u201335, 1983.","journal-title":"SIAM J. Computing"},{"issue":"3","key":"1_CR10","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0206043","volume":"6","author":"D.T. Lee","year":"1977","unstructured":"D.T. Lee and F.P. Preparata, \u201cLocation of a Point in a Planar Subdivision and its Applications,\u201d SIAM J. Computing, vol 6, no. 3, pp. 594\u2013606, 1977.","journal-title":"SIAM J. Computing"},{"issue":"3","key":"1_CR11","doi-asserted-by":"crossref","first-page":"636","DOI":"10.4153\/CJM-1975-074-0","volume":"27","author":"D. Kelly","year":"1975","unstructured":"D. Kelly and I. Rival, \u201cPlanar Lattices,\u201d Canadian J. Mathematics, vol. 27, no. 3, pp. 636\u2013665, 1975.","journal-title":"Canadian J. Mathematics"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"R.J. Lipton and R.E. Tarjan, \u201cApplications of a Planar Separator Theorem,\u201d Proc. 18th IEEE Symp. on Foundations of Computer Science, pp. 162\u2013170, 1977.","DOI":"10.1109\/SFCS.1977.6"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry, Springer-Verlag, 1984.","DOI":"10.1007\/978-3-642-69900-9_2"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"M. Overmars, \u201cRange Searching in a Set of Line Segments,\u201d Proc. ACM Symp. on Computational Geometry, pp. 177\u2013185, 1985.","DOI":"10.1145\/323233.323257"},{"issue":"3","key":"1_CR15","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1137\/0210035","volume":"10","author":"F.P. Preparata","year":"1981","unstructured":"F.P. Preparata, \u201cA New Approach to Planar Point Location,\u201d SIAM J. Computing, vol. 10, no. 3, pp. 473\u2013483, 1981.","journal-title":"SIAM J. Computing"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"F.P. Preparata and M.I. Shamos, Computational Geometry, Springer-Verlag, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"F.P. Preparata and R. Tamassia, \u201cFully Dynamic Techniques for Point Location and Transitive Closure in Planar Structures,\u201d Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988 (to appear).","DOI":"10.1109\/SFCS.1988.21972"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"F.P. Preparata and R. Tamassia, \u201cDynamic Planar Point Location with Optimal Query time,\u201d manuscript submitted for publication, 1988.","DOI":"10.1007\/BFb0028975"},{"issue":"7","key":"1_CR19","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak and R.E. Tarjan, \u201cPlanar Point Location Using Persistent Search Trees,\u201d Communications ACM, vol. 29, no. 7, pp. 669\u2013679, 1986.","journal-title":"Communications ACM"},{"key":"1_CR20","unstructured":"R.E. Tarjan, \u201cData Structures and Network Algorithms,\u201d CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial Applied Mathematics, 1983."},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"R. Tamassia, \u201cDynamic Data Structures for Two-dimensional Searching,\u201d Ph.D Thesis, University of Illinois; August 1988.","DOI":"10.21236\/ADA201173"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50517-2_67","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T21:36:50Z","timestamp":1640900210000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50517-2_67"}},"subtitle":["Invited paper"],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540505174","9783540460305"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-50517-2_67","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}