{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:32:11Z","timestamp":1725456731179},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540508403"},{"type":"electronic","value":"9783540460985"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"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":[[1989]]},"DOI":"10.1007\/bfb0028975","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T00:28:19Z","timestamp":1133396899000},"page":"84-95","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Dynamic planar point location with optimal query time"],"prefix":"10.1007","author":[{"given":"Franco P.","family":"Preparata","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,16]]},"reference":[{"issue":"3","key":"7_CR1","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"S.W. Bent","year":"1985","unstructured":"S.W. Bent, D.D. Sleator, and R.E. Tarjan, \u201cBiased Search Trees,\u201d SIAM J. Computing, vol. 14, no. 3, pp. 545\u2013568, 1985.","journal-title":"SIAM J. Computing"},{"issue":"2","key":"7_CR2","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":"7_CR3","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":"7_CR4","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":"7_CR5","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":"7_CR6","doi-asserted-by":"crossref","unstructured":"O. Fries, K. Mehlhorn, and S. Naeher, \u201cDynamization of Geometric Data Structures,\u201d Proc. ACM Symp. on Computational Geometry, pp. 168\u2013176, 1985.","DOI":"10.1145\/323233.323256"},{"issue":"1","key":"7_CR7","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":"7_CR8","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"},{"key":"7_CR9","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":"7_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69900-9","volume-title":"Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn, Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry, Springer-Verlag, New York, 1984."},{"key":"7_CR11","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":"7_CR12","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":"7_CR13","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, pp. 558\u2013567, 1988.","DOI":"10.1109\/SFCS.1988.21972"},{"key":"7_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F.P. Preparata","year":"1985","unstructured":"F.P. Preparata and M.I. Shamos, Computational Geometry, Springer-Verlag, New York, 1985."},{"issue":"7","key":"7_CR15","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":"7_CR16","doi-asserted-by":"crossref","unstructured":"R. Tamassia, \u201cDynamic Data Structures for Two-Dimensional Searching,\u201d Ph.D. Thesis (Technical Report ACT-100), Coordinated Science Laboratory, Univ. of Illinois at Urbana-Champaign, 1988.","DOI":"10.21236\/ADA201173"}],"container-title":["Lecture Notes in Computer Science","STACS 89"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028975","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:30:18Z","timestamp":1578526218000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028975"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540508403","9783540460985"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/bfb0028975","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"16 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}