{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:00Z","timestamp":1725663360691},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540529217"},{"type":"electronic","value":"9783540471776"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52921-7_73","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:47:51Z","timestamp":1330206471000},"page":"241-250","source":"Crossref","is-referenced-by-count":2,"title":["Spatial point location and its applications"],"prefix":"10.1007","author":[{"given":"Xue-Hou","family":"Tan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomio","family":"Hirata","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasuyoshi","family":"Inagaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1109\/TC.1980.1675628","volume":"29","author":"J.L. Bentley","year":"1980","unstructured":"J.L. Bentley and D. Wood, An optimal worst-case algorithm for reporting intersections of rectangles, IEEE Trans. on Comput. C-29(1980), 571\u2013577.","journal-title":"IEEE Trans. on Comput."},{"key":"25_CR2","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, How to search in history, Inform. Control 64(1985), 77\u201399.","journal-title":"Inform. Control"},{"key":"25_CR3","unstructured":"B.Chazelle and H.Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, in Proceedings, 29th Annu. IEEE Symp. Found. of Comput. Sci.(1988), pp. 590\u2013600."},{"key":"25_CR4","unstructured":"B.Chazelle and J.Friedman, A deterministic view of random sampling and its use in geometry, in Proceedings, 29th Annu. IEEE Symp. Found. of Comput. Sci.(1988), pp. 539\u2013548."},{"key":"25_CR5","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K.L. Clarkson","year":"1987","unstructured":"K.L. Clarkson, New applications of random sampling in computational geometry, Discrete Comput. Geometry 2(1987), 195\u2013222.","journal-title":"Discrete Comput. Geometry"},{"key":"25_CR6","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, Searching and storing similar lists, J. Algorithms 7(1986), 202\u2013220.","journal-title":"J. Algorithms"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"P.Dietz and D.D.Sleator, Two algorithms for maintaining order in a list, in Proceedings, 19th Annu. ACM Symp. Theory of Computing(1987), pp. 365\u2013372.","DOI":"10.1145\/28395.28434"},{"key":"25_CR8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"D. Dobkin","year":"1976","unstructured":"D. Dobkin and R.J. Lipton, Multidimensional search problems, SIAM J. Comput. 5(1976), 181\u2013186.","journal-title":"SIAM J. Comput."},{"key":"25_CR9","doi-asserted-by":"publisher","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 and R.T. Tarjan, Making data structures persistent, J. Comput. Sys. Sci. 38(1989), 86\u2013124.","journal-title":"J. Comput. Sys. Sci."},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"H.Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.","DOI":"10.1007\/978-3-642-61568-9"},{"key":"25_CR11","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/0020-0190(82)90090-4","volume":"14","author":"H. Edelsbrunner","year":"1982","unstructured":"H. Edelsbrunner, H.A. Maurer and D.G. Kirkpatrick, Polygonal intersection searching, Inform. Process. Lett. 14(1982), 74\u201377.","journal-title":"Inform. Process. Lett."},{"key":"25_CR12","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0734-189X(84)90142-7","volume":"28","author":"H. Edelsbrunner","year":"1984","unstructured":"H. Edelsbrunner, M.H. Overmars and R. Seidel, Some methods of computational geometry applied to computer graphics, Comput. Vision Graphics Image Process. 28(1984), 92\u2013108.","journal-title":"Comput. Vision Graphics Image Process"},{"key":"25_CR13","unstructured":"L.J.Guibas and R.Sedgewick, A dichromatic framework for balanced trees, in Proceedings, 19th Annu. IEEE Symp. Found. of Comput. Sci.(1978), pp. 8\u201321."},{"key":"25_CR14","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/27625.27627","volume":"6","author":"M. McKenna","year":"1987","unstructured":"M. McKenna, Worst case optimal hidden surface removal, ACM Trans. Graphics 6, 1987, 19\u201328.","journal-title":"ACM Trans. Graphics"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1145\/358656.358681","volume":"25","author":"J. Nivergelt","year":"1982","unstructured":"J. Nivergelt and F.P. Preparata, Plane sweep algorithms for intersecting geometric figures, Comm. ACM 25(1982), 739\u2013747.","journal-title":"Comm. ACM"},{"key":"25_CR16","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1007\/BF01935366","volume":"25","author":"O. Nurmi","year":"1985","unstructured":"O. Nurmi, A fast line-sweep algorithm for hidden line elimination, BIT 25(1985), 466\u2013472.","journal-title":"BIT"},{"key":"25_CR17","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/S0734-189X(86)80028-7","volume":"36","author":"O. Nurmi","year":"1986","unstructured":"O. Nurmi, On translating a set of objects in 2-and 3-dimensional space, Comput. Vision Graphics Image Process. 36(1986), 42\u201352.","journal-title":"Comput. Vision Graphics Image Process."},{"key":"25_CR18","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":"25_CR19","unstructured":"F.P.Preparata and R.Tamassia, Fully dynamic techniques for point location and transitive closure in planar structures, in Proceedings, 29th Annu. IEEE Symp. Found. of Comput. Sci.(1988), pp. 558\u2013567."},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1137\/0218056","volume":"18","author":"F.P. Preparata","year":"1989","unstructured":"F.P. Preparata and R. Tamassia, Fully dynamic point location in a monotone subdivision, SIAM J. Comput. 18(1989), 811\u2013830.","journal-title":"SIAM J. Comput."},{"key":"25_CR21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/3-540-51542-9_2","volume":"382","author":"F.P. Preparata","year":"1989","unstructured":"F.P. Preparata and R. Tamassia, Efficient spatial point location, in Algorithms and Data Structures (WADS'89), Lect. Notes in Comput. Sci. 382, Springer-Verlag, 1989, pp. 3\u201311.","journal-title":"Lect. Notes in Comput. Sci."},{"key":"25_CR22","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, Planar point location using persistent search trees, Comm. ACM 29(1986), 669\u2013679.","journal-title":"Comm. ACM"},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"A.Schmitt, H.M\u00fcller and W.Leister, Ray tracing algorithms \u2014 theory and practice, Proc. NATO Advanced Study Inst. Theoret. Found. Comput. Graphics and CAD, Springer-Verlag, 1987, pp. 997\u20131029.","DOI":"10.1007\/978-3-642-83539-1_42"}],"container-title":["Lecture Notes in Computer Science","Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52921-7_73.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:25:49Z","timestamp":1605648349000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52921-7_73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540529217","9783540471776"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-52921-7_73","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}