{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T05:46:47Z","timestamp":1743140807504,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540425120"},{"type":"electronic","value":"9783540446910"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"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":[[2001]]},"DOI":"10.1007\/3-540-44691-5_16","type":"book-chapter","created":{"date-parts":[[2007,6,2]],"date-time":"2007-06-02T22:32:07Z","timestamp":1180823527000},"page":"183-194","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Planar Point Location for Large Data Sets: To Seek or Not to Seek"],"prefix":"10.1007","author":[{"given":"Jan","family":"Vahrenhold","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus H.","family":"Hinrichs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,24]]},"reference":[{"key":"16_CR1","unstructured":"U. Adamy and R. Seidel. On the exact worst case query complexity of planar point location. Proc. 9th Annual ACM-SIAM Symp. Discrete Algorithms, 609\u2013618. 1998."},{"key":"16_CR2","unstructured":"P. Agarwal, L. Arge, G. Brodal, and J. Vitter. I\/O-effcient dynamic point location in monotone planar subdivisions. Proc. 10th Annual ACM-SIAM Symp. Discrete Algorithms, 11\u201320. 1999."},{"issue":"9","key":"16_CR3","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal and J. Vitter. The input\/output complexity of sorting and related problems. Comm. ACM, 31(9):1116\u20131127, 1988.","journal-title":"Comm. ACM"},{"key":"16_CR4","unstructured":"L. Arge, R. Barve, O. Procopiuc, L. Toma, D. Vengro., and R. Wickremesinghe. TPIE user manual and reference, edition 0.9.01a. Duke University, North Carolina, < http:\/\/www.cs.duke.edu\/TPIE\/ >, 1999. (accessed 12 Jul. 1999)."},{"key":"16_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/3-540-46439-5_29","volume-title":"A unified approach for indexed and non-indexed spatial join","author":"L. Arge","year":"2000","unstructured":"L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, J. Vahrenhold, and J. Vitter. A unified approach for indexed and non-indexed spatial join. Proc. 7th Intl. Conf. Extending Databases Technology, LNCS 1777, 413\u2013429. 2000."},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"L. Arge and J. Vahrenhold. I\/O-effcient dynamic planar point location. Proc. 16th Annual ACM Symp. Computational Geometry, 191\u2013200. 2000.","DOI":"10.1145\/336154.336205"},{"key":"16_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/3-540-60313-1_151","volume-title":"External-memory algorithms for processing line segments in geographic information systems","author":"L. Arge","year":"1995","unstructured":"L. Arge, D. Vengro., and J. Vitter. External-memory algorithms for processing line segments in geographic information systems. Proc. 3rd Annual European Symp. Algorithms, LNCS 979, 295\u2013310. 1995."},{"key":"16_CR8","unstructured":"K. Baumann. Implementation and comparison of five algorithms for point-location in trapezoidal decompositions. Master\u2019s thesis, Fachbereich Mathematik und Informatik, Westf\u00e4lische Wilhelms-Universit\u00e4t M\u00fcnster, Germany, 1996. (in German)."},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle and L. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1:133\u2013162, 1986.","journal-title":"Algorithmica"},{"issue":"4","key":"16_CR10","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0925-7721(97)00020-5","volume":"9","author":"Y.-J. Chiang","year":"1998","unstructured":"Y.-J. Chiang. Experiments on the practical I\/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep. Computational Geometry: Theory and Applications, 9(4):211\u2013236, March 1998.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer, and E. Ramos. Randomized external-memory algorithms for some geometric problems. Proc. 14th Annual ACM Symp. Computational Geometry, 259-268. 1998.","DOI":"10.1145\/276884.276914"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"D. Dobkin","year":"1976","unstructured":"D. Dobkin and R. Lipton. Multidimensional searching problems. SIAM J. Comput., 5:181\u2013186, 1976.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"16_CR13","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/357337.357338","volume":"3","author":"M. Edahiro","year":"1984","unstructured":"M. Edahiro, I. Kokubo, and T. Asano. A new point-location algorithm and its practical efficiency: Comparison with existing algorithms. ACM Trans. Graphics, 3(2):86\u2013109, 1984.","journal-title":"ACM Trans. Graphics"},{"issue":"2","key":"16_CR14","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, L. Guibas, and J. Stol.. Optimal point location in a monotone subdivision. SIAM J. Comput., 15(2):317\u2013340, 1986.","journal-title":"SIAM J. Comput."},{"key":"16_CR15","unstructured":"W. R. Franklin. Adaptive grids for geometric operations. Proc. 6th Intl. Symp. Automated Cartography (Auto-Carto Six), vol. 2, 230\u2013239. 1983."},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"M. Goodrich, J.-J. Tsay, D. Vengro., and J. Vitter. External-memory computational geometry. Proc. 34th Annual IEEE Symp. Found. Computer Science, 714\u2013723. 1993.","DOI":"10.1109\/SFCS.1993.366816"},{"key":"16_CR17","unstructured":"K. Kim and S. Cha. Sibling clustering of tree-based spatial indexes for efficient spatial query processing. Proc. 1998 ACM CIKM Intl. Conf. Information and Knowledge Management, 398\u2013405. 1998."},{"issue":"1","key":"16_CR18","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"D. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Comput., 12(1):28\u201335, 1983.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"16_CR19","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/0020-0190(79)90066-8","volume":"9","author":"D.-T. Lee","year":"1979","unstructured":"D.-T. Lee and C. Yang. Location of multiple points in a planar subdivision. Inf. Proc. Letters, 9(4):190\u2013193, 1979.","journal-title":"Inf. Proc. Letters"},{"key":"16_CR20","unstructured":"K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, 1994."},{"key":"16_CR21","unstructured":"D. Musser and A. Saini. STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library. Addison-Wesley, 1996."},{"key":"16_CR22","unstructured":"F. Preparata and M. Shamos. Computational Geometry: An Introduction. Springer, 2nd edition, 1988."},{"key":"16_CR23","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak and R. Tarjan. Planar point location using persistent search trees. Comm. ACM, 29:669\u2013679, 1986.","journal-title":"Comm. ACM"},{"key":"16_CR24","unstructured":"J. Snoeyink. Point location. Handbook of Discrete and Computational Geometry, Discrete Mathematics and its Applications, chapter 30, 559\u2013574. CRC Press, 1997."},{"key":"16_CR25","unstructured":"U.S. Geological Survey. 1:100,000-scale digital line graphs (DLG). http:\/\/edcwww.cr.usgs.gov\/doc\/edchome\/ndcdb\/ndcdb.html (accessed 26 May 1999)."},{"key":"16_CR26","unstructured":"J. Vahrenhold. External Memory Algorithms for Geographic Information Systems. PhD thesis, Fachbereich Mathematik und Informatik,Westf\u00e4lische Wilhelms-Universit\u00e4t M\u00fcnster, Germany, 1999."},{"key":"16_CR27","unstructured":"D. Vengro. A transparent parallel I\/O environment. In Proc. DAGS Symp., 1994."}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44691-5_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T21:47:33Z","timestamp":1737064053000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44691-5_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540425120","9783540446910"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-44691-5_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"24 August 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}