{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T18:43:57Z","timestamp":1755801837028,"version":"3.44.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T00:00:00Z","timestamp":1538092800000},"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":["Algorithmica"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s00453-018-0518-2","type":"journal-article","created":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T10:33:23Z","timestamp":1538130803000},"page":"1921-1937","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Building an Optimal Point-Location Structure in $$O( sort (n))$$ O ( s o r t ( n ) ) I\/Os"],"prefix":"10.1007","volume":"81","author":[{"given":"Xiaocheng","family":"Hu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng","family":"Sheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,28]]},"reference":[{"issue":"14","key":"518_CR1","first-page":"1834","volume":"6","author":"D Achakeev","year":"2013","unstructured":"Achakeev, D., Seeger, B.: Efficient bulk updates on multiversion B-trees. PVLDB 6(14), 1834\u20131845 (2013)","journal-title":"PVLDB"},{"issue":"1","key":"518_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00454-009-9177-z","volume":"42","author":"P Afshani","year":"2009","unstructured":"Afshani, P., Chan, T.M.: On approximate range counting and depth. Discrete Comput. Geom. 42(1), 3\u201321 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"518_CR3","unstructured":"Agarwal, P.K., Arge, L.., Brodal, G.S.., Vitter, J.S.: I\/O-efficient dynamic point location in monotone planar subdivisions. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 11\u201320 (1999)"},{"issue":"9","key":"518_CR4","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. CACM 31(9), 1116\u20131127 (1988)","journal-title":"CACM"},{"key":"518_CR5","doi-asserted-by":"crossref","unstructured":"Arge, L., Brodal, G.S., Georgiadis, L.: Improved dynamic planar point location. In: Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 305\u2013314 (2006)","DOI":"10.1109\/FOCS.2006.40"},{"issue":"1\u20132","key":"518_CR6","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/s00453-011-9541-2","volume":"63","author":"L Arge","year":"2012","unstructured":"Arge, L., Brodal, G.S., Rao, S.S.: External memory planar point location with logarithmic updates. Algorithmica 63(1\u20132), 457\u2013475 (2012)","journal-title":"Algorithmica"},{"key":"518_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/996546.996549","volume":"8","author":"L Arge","year":"2003","unstructured":"Arge, L., Danner, A., Teh, S.-M.: I\/O-efficient point location using persistent B-trees. ACM J. Exp. Algorithmics 8, 1\u20132 (2003)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"2","key":"518_CR8","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.comgeo.2003.04.001","volume":"29","author":"L Arge","year":"2004","unstructured":"Arge, L., Vahrenhold, J.: I\/O-efficient dynamic planar point location. Comput. Geom. 29(2), 147\u2013162 (2004)","journal-title":"Comput. Geom."},{"issue":"1","key":"518_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-006-1208-z","volume":"47","author":"L Arge","year":"2007","unstructured":"Arge, L., Vengroff, D.E., Vitter, J.S.: External-memory algorithms for processing line segments in geographic information systems. Algorithmica 47(1), 1\u201325 (2007)","journal-title":"Algorithmica"},{"issue":"3","key":"518_CR10","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1137\/060669474","volume":"38","author":"B Aronov","year":"2008","unstructured":"Aronov, B., Har-Peled, S.: On approximating the depth and related problems. SIAM J. Comput. 38(3), 899\u2013921 (2008)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"518_CR11","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1006\/jagm.1994.1040","volume":"17","author":"H Baumgarten","year":"1994","unstructured":"Baumgarten, H., Jung, H., Mehlhorn, K.: Dynamic point location in general subdivisions. J. Algorithms 17(3), 342\u2013380 (1994)","journal-title":"J. Algorithms"},{"key":"518_CR12","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Cole, R., Raman, R.: Exponential structures for efficient cache-oblivious algorithms. In: International Colloquium on Automata, Languages and Programming (ICALP), pp. 195\u2013207 (2002)","DOI":"10.1007\/3-540-45465-9_18"},{"issue":"4","key":"518_CR13","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"JL Bentley","year":"1980","unstructured":"Bentley, J.L., Saxe, J.B.: Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms 1(4), 301\u2013358 (1980)","journal-title":"J. Algorithms"},{"key":"518_CR14","doi-asserted-by":"crossref","unstructured":"Bertino, E., Catania, B., Shidlovsky, B.: Towards optimal indexing for segment databases. In: Proceedings of Extending Database Technology (EDBT), pp. 39\u201353 (1998)","DOI":"10.1007\/BFb0100976"},{"issue":"5","key":"518_CR15","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1137\/0221057","volume":"21","author":"S-W Cheng","year":"1992","unstructured":"Cheng, S.-W., Janardan, R.: New results on dynamic planar point location. SIAM J. Comput. 21(5), 972\u2013999 (1992)","journal-title":"SIAM J. Comput."},{"key":"518_CR16","doi-asserted-by":"crossref","unstructured":"de Berg, M., Haverkort, H.J., Thite, S., Toma, L.: I\/O-efficient map overlay and point location in low-density subdivisions. In: International Symposium on Algorithms and Computation (ISAAC), pp. 500\u2013511 (2007)","DOI":"10.1007\/978-3-540-77120-3_44"},{"key":"518_CR17","unstructured":"den Bercken, J.V., Seeger, B., Widmayer, P.: A generic approach to bulk loading multidimensional index structures. In: Proceedings of Very Large Data Bases (VLDB), pp. 406\u2013415 (1997)"},{"key":"518_CR18","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Tsay, J.-J., Vengroff, D.E., Vitter, J.S.: External-memory computational geometry. In: Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 714\u2013723 (1993)","DOI":"10.1109\/SFCS.1993.366816"},{"key":"518_CR19","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"518_CR20","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1137\/S0097539705446925","volume":"38","author":"A Maheshwari","year":"2008","unstructured":"Maheshwari, A., Zeh, N.: I\/O-efficient planar separators. SIAM J. Comput. 38(3), 767\u2013801 (2008)","journal-title":"SIAM J. Comput."},{"key":"518_CR21","doi-asserted-by":"crossref","unstructured":"Overmars, M.H.: Range searching in a set of line segments. In: Proceedings of Symposium on Computational Geometry (SoCG), pp. 177\u2013185 (1985)","DOI":"10.1145\/323233.323257"},{"key":"518_CR22","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Thorup, M.: Time\u2013space trade-offs for predecessor search. In: Proceedings of ACM Symposium on Theory of Computing (STOC), pp. 232\u2013240 (2006)","DOI":"10.1145\/1132516.1132551"},{"issue":"7","key":"518_CR23","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N Sarnak","year":"1986","unstructured":"Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. CACM 29(7), 669\u2013679 (1986)","journal-title":"CACM"},{"key":"518_CR24","unstructured":"van Walderveen, F., Zeh, N., Arge, L.: Multiway simple cycle separators and i\/o-efficient algorithms for planar graphs. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 901\u2013918 (2013)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0518-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0518-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0518-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,20]],"date-time":"2025-08-20T23:54:37Z","timestamp":1755734077000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0518-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,28]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["518"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0518-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,9,28]]},"assertion":[{"value":"30 April 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}