{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T05:13:58Z","timestamp":1737695638272,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540771180"},{"type":"electronic","value":"9783540771203"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-77120-3_44","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T11:31:09Z","timestamp":1196940669000},"page":"500-511","source":"Crossref","is-referenced-by-count":2,"title":["I\/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions"],"prefix":"10.1007","author":[{"given":"Mark","family":"de Berg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Herman","family":"Haverkort","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shripad","family":"Thite","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laura","family":"Toma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"44_CR1","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. Commun. ACM\u00a031, 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"doi-asserted-by":"crossref","unstructured":"Arge, L., Vahrenhold, J.: I\/O-efficient dynamic planar point location. In: Proc. 16th Annu. ACM Symp. Comput. Geom., pp. 191\u2013200 (2000)","key":"44_CR2","DOI":"10.1145\/336154.336205"},{"doi-asserted-by":"crossref","unstructured":"Arge, L., Vengroff, D.E., Vitter, J.S.: External-memory algorithms for processing line segments in geographic information systems. In: Proc. 3th Annu. European Symp. Algorithms, pp. 295\u2013310 (1995)","key":"44_CR3","DOI":"10.1007\/3-540-60313-1_151"},{"key":"44_CR4","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0925-7721(00)00022-5","volume":"17","author":"S. Arya","year":"2000","unstructured":"Arya, S., Mount, D.M.: Approximate range searching. Comput. Geom. Theory Appl.\u00a017, 135\u2013152 (2000)","journal-title":"Comput. Geom. Theory Appl."},{"key":"44_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/3-540-45465-9_18","volume-title":"Automata, Languages and Programming","author":"M. Bender","year":"2002","unstructured":"Bender, M., Cole, R., Raman, R.: Exponential structures for efficient cache-oblivious algorithms. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 195\u2013207. Springer, Heidelberg (2002)"},{"unstructured":"Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious B-trees. In: Proc. 41th Annu. IEEE Symp. Found. Comput. Sci., pp. 339\u2013409 (2000)","key":"44_CR6"},{"doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Jacob, R.: Cache oblivious search trees via binary trees of small height. In: Proc. 13th ACM-SIAM Symp. Discrete Algorithms, pp. 39\u201348 (2002)","key":"44_CR7","DOI":"10.7146\/brics.v8i36.21696"},{"unstructured":"Chiang, Y.-J., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-Memory Graph Algorithms. In: Proc. 6th ACM-SIAM Symp. Discrete Algorithms, pp. 139\u2013149 (1995)","key":"44_CR8"},{"key":"44_CR9","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press \/ McGraw-Hill, Cambridge, Mass (2001)"},{"issue":"3","key":"44_CR10","doi-asserted-by":"publisher","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. Comput. Geom. Theory Appl.\u00a011(3), 305\u2013337 (2001)","journal-title":"Comput. Geom. Theory Appl."},{"key":"44_CR11","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s004530010047","volume":"28","author":"M. Berg de","year":"2000","unstructured":"de Berg, M.: Linear size binary space partitions for uncluttered scenes. Algorithmica\u00a028, 353\u2013366 (2000)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"de Berg, M.: Improved bounds on the union complexity of fat objects. In: Proc. 25th Conf. Found. Soft. Tech. Theoret. Comput. Sci., pp. 116\u2013127 (2005)","key":"44_CR12","DOI":"10.1007\/11590156_9"},{"key":"44_CR13","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s00453-002-0961-x","volume":"34","author":"M. Berg de","year":"2002","unstructured":"de Berg, M., Katz, M.J., Stappen, A.v., Vleugels, J.: Realistic input models for geometric algorithms. Algorithmica\u00a034, 81\u201397 (2002)","journal-title":"Algorithmica"},{"key":"44_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04245-8","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2000","unstructured":"de Berg, M., van Kreveld, M., Overmars, M.H., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Heidelberg (2000)","edition":"2"},{"doi-asserted-by":"crossref","unstructured":"Finke, U., Hinrichs, K.: Overlaying simply connected planar subdivisions in linear time. In: Proc. 11th Annu. ACM Symp. Comput. Geom., pp. 119\u2013126 (1995)","key":"44_CR15","DOI":"10.1145\/220279.220292"},{"doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proc. 40th Annu. IEEE Symp. Found. Comput. Sci., pp. 285\u2013298 (1999)","key":"44_CR16","DOI":"10.1109\/SFFCS.1999.814600"},{"issue":"12","key":"44_CR17","doi-asserted-by":"publisher","first-page":"905","DOI":"10.1145\/358728.358741","volume":"25","author":"I. Gargantini","year":"1982","unstructured":"Gargantini, I.: An effective way to represent quadtrees. Commun. ACM\u00a025(12), 905\u2013910 (1982)","journal-title":"Commun. ACM"},{"doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Tsay, J.-J., Vengroff, D.E., Vitter, J.S.: External-memory computational geometry. In: Proc. 34th Annu. IEEE Symp. Found. Comput. Sci., pp. 714\u2013723 (1993)","key":"44_CR18","DOI":"10.1109\/SFCS.1993.366816"},{"key":"44_CR19","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s00778-002-0067-8","volume":"11","author":"G.R. Hjaltason","year":"2002","unstructured":"Hjaltason, G.R., Samet, H.: Speeding up construction of PMR quadtree-based spatial indexes. VLDB Journal\u00a011, 137\u2013190 (2002)","journal-title":"VLDB Journal"},{"key":"44_CR20","volume-title":"Spatial Data Structures: Quadtrees, Octrees, and Other Hierarchical Methods","author":"H. Samet","year":"1989","unstructured":"Samet, H.: Spatial Data Structures: Quadtrees, Octrees, and Other Hierarchical Methods. Addison-Wesley, Reading, MA (1989)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77120-3_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T08:11:34Z","timestamp":1737619894000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77120-3_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540771180","9783540771203"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77120-3_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}