{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:42:46Z","timestamp":1725486166685},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540430025"},{"type":"electronic","value":"9783540452942"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45294-x_21","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T02:45:12Z","timestamp":1181616312000},"page":"244-255","source":"Crossref","is-referenced-by-count":1,"title":["I\/O-Efficient Batched Range Counting and Its Applications to Proximity Problems"],"prefix":"10.1007","author":[{"given":"Tam\u00e1s","family":"Lukovszki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Norbert","family":"Zeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,11,26]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal, J. Erickson. Geometric range searching and its relatives. Advances in Disc. and Comp. Geom., pp. 1\u201356. AMS, 1999.","DOI":"10.1090\/conm\/223\/03131"},{"key":"21_CR2","unstructured":"L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, J. S. Vitter. Theory and practice of I\/O-efficient algorithms for multidimensional batched searching problems. Proc. SODA, 1998."},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"L. Arge, V. Samoladas, J. S. Vitter. On two-dimensional indexability and optimal range search indexing. Proc. PODS\u201999, 1999.","DOI":"10.1145\/303976.304010"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"L. Arge. The buffer tree: A new technique for optimal I\/O-algorithms. Proc. WADS, pp. 334\u2013345, 1995.","DOI":"10.1007\/3-540-60220-8_74"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"L. Arge, P. B. Miltersen. On showing lower bounds for external-memory computational geometry problems. In J. Abello and J. S. Vitter (eds.), External Memory Algorithms and Visualization. AMS, 1999.","DOI":"10.1090\/dimacs\/050\/08"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"L. Arge, D. E. Vengro., J. S. Vitter. External-memory algorithms for processing line segments in geographic information systems. Proc. ESA, pp. 295\u2013310, 1995.","DOI":"10.1007\/3-540-60313-1_151"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"L. Arge, J. S. Vitter. Optimal dynamic interval management in external memory. Proc. FOCS, pp. 560\u2013569, 1996.","DOI":"10.1109\/SFCS.1996.548515"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"S. Arya, G. Das, D. M. Mount, J. S. Salowe, M. Smid. Euclidean spanners: Short, thin, and lanky. Proc. STOC, pp. 489\u2013498, 1995.","DOI":"10.1145\/225058.225191"},{"key":"21_CR9","unstructured":"Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengro., J. S. Vitter. External-memory graph algorithms. Proc. SODA, 1995."},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"P. B. Callahan, S. R. Kosaraju. A decomposition of multi-dimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Proc. STOC, pp. 546\u2013556, 1992.","DOI":"10.1145\/129712.129766"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson. Approximation algorithms for shortest path motion planning. Proc. STOC, pp. 56\u201365, 1987.","DOI":"10.1145\/28395.28402"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"M. Fischer, T. Lukovszki, M. Ziegler. Geometric searching in walkthrough animations with weak spanners in real time. Proc. ESA, pp. 163\u2013174, 1998.","DOI":"10.1007\/3-540-68530-8_14"},{"key":"21_CR13","unstructured":"M. T. Goodrich, J.-J. Tsay, D. E. Vengro., J. S. Vitter. External-memory computational geometry. Proc. FOCS, 1993."},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"S. Govindarajan, T. Lukovszki, A. Maheshwari, N. Zeh. I\/O-efficient well-separated pair decomposition and its applications. Proc. ESA, pp. 220\u2013231, 2000.","DOI":"10.1007\/3-540-45253-2_21"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Y. Hassin, D. Peleg. Sparse communication networks and efficient routing in the plane. Proc. PODC, 2000.","DOI":"10.1145\/343477.343514"},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF02187821","volume":"7","author":"J. M. Keil","year":"1992","unstructured":"J. M. Keil, C. A. Gutwin. Classes of graphs which approximate the complete Euclidean graph. Discrete & Computational Geometry, 7:13\u201328, 1992.","journal-title":"Discrete & Computational Geometry"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"C. Levcopoulos, G. Narasimhan, M. Smid. Efficient algorithms for constructing fault-tolerant geometric spanners. Proc. STOC, pp. 186\u2013195, 1998.","DOI":"10.1145\/276698.276734"},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"T. Lukovszki. New results on fault tolerant geometric spanners. Proc. WADS, pp. 193\u2013204, 1999.","DOI":"10.1007\/3-540-48447-7_20"},{"key":"21_CR19","unstructured":"J. Ruppert, R. Seidel. Approximating the d-dimensional complete Euclidean graph. Proc. CCCG, pp. 207\u2013210, 1991."},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"D. E. Vengro., J. S. Vitter. Efficient 3-D range searching in external memory. Proc. STOC, 1996.","DOI":"10.1145\/237814.237864"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"J. S. Vitter. External memory algorithms. Proc. PODS, pp. 119\u2013128, 1998.","DOI":"10.1145\/275487.275501"},{"issue":"2","key":"21_CR22","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/BF01185207","volume":"12","author":"J. S. Vitter","year":"1994","unstructured":"J. S. Vitter, E. A. M. Shriver. Algorithms for parallel memory I: Two-level memories. Algorithmica, 12(2\u20143):110\u2013147, 1994.","journal-title":"Algorithmica"},{"key":"21_CR23","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A. C. Yao","year":"1982","unstructured":"A. C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comp., 11:721\u2013736, 1982.","journal-title":"SIAM J. Comp."}],"container-title":["Lecture Notes in Computer Science","FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45294-X_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T01:27:53Z","timestamp":1556501273000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45294-X_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540430025","9783540452942"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-45294-x_21","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}