{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,12]],"date-time":"2023-06-12T15:54:34Z","timestamp":1686585274842},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,6,15]],"date-time":"2011-06-15T00:00:00Z","timestamp":1308096000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00453-011-9541-2","type":"journal-article","created":{"date-parts":[[2011,6,14]],"date-time":"2011-06-14T17:56:03Z","timestamp":1308074163000},"page":"457-475","source":"Crossref","is-referenced-by-count":2,"title":["External Memory Planar Point Location with Logarithmic Updates"],"prefix":"10.1007","volume":"63","author":[{"given":"Lars","family":"Arge","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. Srinivasa","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,6,15]]},"reference":[{"key":"9541_CR1","first-page":"1116","volume-title":"Proc. ACM-SIAM Symposium on Discrete Algorithms","author":"P.K. Agarwal","year":"1999","unstructured":"Agarwal, P.K., Arge, L., Brodal, G.S., Vitter, J.S.: I\/O-efficient dynamic point location in monotone planar subdivisions. In: Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 1116\u20131127 (1999)"},{"issue":"9","key":"9541_CR2","doi-asserted-by":"crossref","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. Commun. ACM 31(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"9541_CR3","first-page":"305","volume-title":"Proc. IEEE Symposium on Foundations of Computer Science","author":"L. Arge","year":"2006","unstructured":"Arge, L., Brodal, G.S., Georgiadis, L.: Improved dynamic planar point location. In: Proc. IEEE Symposium on Foundations of Computer Science, pp. 305\u2013314 (2006)"},{"key":"9541_CR4","first-page":"139","volume-title":"Proc. ACM Symposium on Computational Geometry","author":"L. Arge","year":"2008","unstructured":"Arge, L., Brodal, G.S., Rao, S. Srinivasa: External memory planar point location with logarithmic updates. In: Proc. ACM Symposium on Computational Geometry, pp. 139\u2013147 (2008)"},{"key":"9541_CR5","doi-asserted-by":"crossref","unstructured":"Arge, L., Danner, A., Teh, S.-H.: I\/O-efficient point location using persistent B-trees. ACM J. Exp. Algorithms 8 (2003)","DOI":"10.1145\/996546.996549"},{"key":"9541_CR6","first-page":"685","volume-title":"Proc. ACM-SIAM Symposium on Discrete Algorithms","author":"L. Arge","year":"1998","unstructured":"Arge, L., Procopiuc, O., Ramaswamy, S., Suel, T., Vitter, J.S.: Theory and practice of I\/O-efficient algorithms for multidimensional batched searching problems. In: Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 685\u2013694 (1998)"},{"issue":"2","key":"9541_CR7","doi-asserted-by":"crossref","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":"9541_CR8","doi-asserted-by":"crossref","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":"6","key":"9541_CR9","doi-asserted-by":"crossref","first-page":"1488","DOI":"10.1137\/S009753970240481X","volume":"32","author":"L. Arge","year":"2003","unstructured":"Arge, L., Vitter, J.S.: Optimal external memory interval management. SIAM J. Comput. 32(6), 1488\u20131508 (2003)","journal-title":"SIAM J. Comput."},{"key":"9541_CR10","doi-asserted-by":"crossref","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, 342\u2013380 (1994)","journal-title":"J. Algorithms"},{"key":"9541_CR11","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.: Organization and maintenance of large ordered indexes. Acta Inform. 1, 173\u2013189 (1972)","journal-title":"Acta Inform."},{"issue":"5","key":"9541_CR12","doi-asserted-by":"crossref","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":"9541_CR13","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1137\/S0097539792224516","volume":"25","author":"Y.-J. Chiang","year":"1996","unstructured":"Chiang, Y.-J., Preparata, F.P., Tamassia, R.: A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps. SIAM J. Comput. 25, 207\u2013233 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9541_CR14","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D. Comer","year":"1979","unstructured":"Comer, D.: The ubiquitous B-tree. ACM Comput. Surv. 11(2), 121\u2013137 (1979)","journal-title":"ACM Comput. Surv."},{"issue":"3","key":"9541_CR15","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1142\/S0218195901000523","volume":"11","author":"A. Crauser","year":"2001","unstructured":"Crauser, A., Ferragina, P., Mehlhorn, K., Meyer, U., Ramos, E.: Randomized external-memory algorithms for some geometric problems. Int. J. Comput. Geom. Appl. 11(3), 305\u2013337 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9541_CR16","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1080\/00207168308803364","volume":"13","author":"H. Edelsbrunner","year":"1983","unstructured":"Edelsbrunner, H.: A new approach to rectangle intersections, Part I. Int. J. Comput. Math. 13, 209\u2013219 (1983)","journal-title":"Int. J. Comput. Math."},{"issue":"2","key":"9541_CR17","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput. 15(2), 317\u2013340 (1986)","journal-title":"SIAM J. Comput."},{"key":"9541_CR18","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0304-3975(81)90103-1","volume":"16","author":"H. Edelsbrunner","year":"1981","unstructured":"Edelsbrunner, H., Maurer, H.A.: A space-optimal solution of general region location. Theor. Comput. Sci. 16, 329\u2013336 (1981)","journal-title":"Theor. Comput. Sci."},{"key":"9541_CR19","first-page":"714","volume-title":"Proc. IEEE Symposium on Foundations of Computer Science","author":"M.T. Goodrich","year":"1993","unstructured":"Goodrich, M.T., Tsay, J.-J., Vengroff, D.E., Vitter, J.S.: External-memory computational geometry. In: Proc. IEEE Symposium on Foundations of Computer Science, pp. 714\u2013723 (1993)"},{"key":"9541_CR20","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddleston","year":"1982","unstructured":"Huddleston, S., Mehlhorn, K.: A new data structure for representing sorted lists. Acta Inform. 17, 157\u2013184 (1982)","journal-title":"Acta Inform."},{"issue":"1","key":"9541_CR21","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D.G. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.G.: Optimal search in planar subdivisions. SIAM J. Comput. 12(1), 28\u201335 (1983)","journal-title":"SIAM J. Comput."},{"key":"9541_CR22","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/323233.323257","volume-title":"Proc. ACM Symposium on Computational Geometry","author":"M.H. Overmars","year":"1985","unstructured":"Overmars, M.H.: Range searching in a set of line segments. In: Proc. ACM Symposium on Computational Geometry, pp. 177\u2013185 (1985)"},{"issue":"7","key":"9541_CR23","doi-asserted-by":"crossref","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. Commun. ACM 29(7), 669\u2013679 (1986)","journal-title":"Commun. ACM"},{"key":"9541_CR24","series-title":"Lecture Notes in Computer Science","first-page":"184","volume-title":"Proc. Workshop on Algorithm Engineering","author":"J. Vahrenhold","year":"2001","unstructured":"Vahrenhold, J., Hinrichs, K.H.: Planar point location for large data sets: To seek or not to seek. In: Proc. Workshop on Algorithm Engineering. Lecture Notes in Computer Science, vol.\u00a01982, pp. 184\u2013194 (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9541-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9541-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9541-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T10:47:51Z","timestamp":1686134871000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9541-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,15]]},"references-count":24,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9541"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9541-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,15]]}}}