{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:53Z","timestamp":1725663293980},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540515425"},{"type":"electronic","value":"9783540482376"}],"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\/3-540-51542-9_2","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:06:34Z","timestamp":1330203994000},"page":"3-11","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Efficient spatial point location"],"prefix":"10.1007","author":[{"given":"Franco P.","family":"Preparata","sequence":"first","affiliation":[]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0019-9958(85)80045-0","volume":"64","author":"B. Chazelle","year":"1985","unstructured":"B. Chazelle, \u201cHow to Search in History,\u201d Information and Control 64 (1985), 77\u201399.","journal-title":"Information and Control"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"B. Chazelle & J. Friedman, \u201cA Deterministic View of Random Sampling and its use in Geometry,\u201d Proc. 29th IEEE Symp. on Foundations of Computer Science (1988), 539\u2013548.","DOI":"10.1109\/SFCS.1988.21970"},{"key":"2_CR3","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle & L.J. Guibas, \u201cFractional Cascading: I. A Data Structuring Technique,\u201d Algorithmica 1 (1986), 133\u2013162.","journal-title":"Algorithmica"},{"key":"2_CR4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. L. Clarkson","year":"1987","unstructured":"K.L. Clarkson, \u201cNew Applications of Random Sampling in Computational Geometry,\u201d Discrete & Computational Geometry 2 (1987), 195\u2013222.","journal-title":"Discrete & Computational Geometry"},{"key":"2_CR5","doi-asserted-by":"publisher","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 Lists,\u201d J. of Algorithms 7 (1986), 202\u2013220.","journal-title":"J. of Algorithms"},{"key":"2_CR6","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"J. R. Driscoll","year":"1989","unstructured":"J.R. Driscoll, N. Sarnak, D.D. Sleator & R.E. Tarjan, \u201cMaking Data Structures Persistent,\u201d J. Computer and System Sciences 38 (1989), 86\u2013124.","journal-title":"J. Computer and System Sciences"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.","DOI":"10.1007\/978-3-642-61568-9"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"L.J. Guibas & R. Sedgewick, \u201cA Dichromatic Framework for Balanced Trees,\u201d Proc. 19th IEEE Symp. on Foundations of Computer Science (1978), 8\u201321.","DOI":"10.1109\/SFCS.1978.3"},{"key":"2_CR9","doi-asserted-by":"crossref","first-page":"636","DOI":"10.4153\/CJM-1975-074-0","volume":"27","author":"D. Kelly","year":"1975","unstructured":"D. Kelly & I. Rival, \u201cPlanar Lattices,\u201d Canadian J. Mathematics 27 (1975), 636\u2013665.","journal-title":"Canadian J. Mathematics"},{"key":"2_CR10","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0206043","volume":"6","author":"D. T. Lee","year":"1977","unstructured":"D.T. Lee & F.P. Preparata, \u201cLocation of a Point in a Planar Subdivision and its Applications,\u201d SIAM J. Computing 6 (1977), 594\u2013606.","journal-title":"SIAM J. Computing"},{"key":"2_CR11","unstructured":"A. Lempel, S. Even & I. Cederbaum, \u201cAn Algorithm for Planarity Testing of Graphs,\u201d Theory of Graphs, Int. Symposium (1966), 215\u2013232."},{"key":"2_CR12","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 & M.I. Shamos, Computational Geometry, Springer-Verlag, New York, 1985."},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"F.P. Preparata & 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), 558\u2013567.","DOI":"10.1109\/SFCS.1988.21972"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"F.P. Preparata & R. Tamassia, \u201cFully Dynamic Point Location in a Monotone Subdivision,\u201d SIAM J. Computing 18 (1989, to appear).","DOI":"10.1137\/0218056"},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak & R.E. Tarjan, \u201cPlanar Point Location Using Persistent Search Trees,\u201d Communications ACM 29 (1986), 669\u2013679.","journal-title":"Communications ACM"},{"key":"2_CR16","unstructured":"R. Tamassia & F.P. Preparata, \u201cDynamic Maintenance of Planar Digraphs, with Applications,\u201d Algorithmica (1989, to appear)."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51542-9_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T00:01:18Z","timestamp":1578528078000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51542-9_2"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540515425","9783540482376"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-51542-9_2","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":"26 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}