{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:40:13Z","timestamp":1742600413462,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540603139"},{"type":"electronic","value":"9783540449133"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"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":[[1995]]},"DOI":"10.1007\/3-540-60313-1_151","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:16:12Z","timestamp":1330280172000},"page":"295-310","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["External-memory algorithms for processing line segments in geographic information systems"],"prefix":"10.1007","author":[{"given":"Lars","family":"Arge","sequence":"first","affiliation":[]},{"given":"Darren Erik","family":"Vengroff","sequence":"additional","affiliation":[]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"issue":"9","key":"22_CR1","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal and J. S. Vitter. The input\/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116\u20131127, Sept. 1988.","journal-title":"Communications of the ACM"},{"key":"22_CR2","unstructured":"D. S. Andrews, J. Snoeyink, J. Boritz, T. Chan, G. Denham, J. Harrison, and C. Zhu. Further comparisons of algorithms for geometric intersection problems. In Proc. 6th Int'l. Symp. on Spatial Data Handling, 1994."},{"key":"22_CR3","unstructured":"ARC\/INFO. Understanding GIS\u2014the ARC\/INFO method. ARC\/INFO, 1993. Rev. 6 for workstations."},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"L. Arge. The buffer tree: A new technique for optimal I\/O-algorithms. In Proc. of 4th Workshop on Algorithms and Data Structures, 1995.","DOI":"10.1007\/3-540-60220-8_74"},{"key":"22_CR5","first-page":"83","volume":"709","author":"L. Arge","year":"1993","unstructured":"L. Arge, M. Knudsen, and K. Larsen. A general lower bound on the I\/O-complexity of comparison-based algorithms. In Proc. of 3rd Workshop on Algorithms and Data Structures, LNCS 709, pages 83\u201394, 1993.","journal-title":"LNCS"},{"key":"22_CR6","unstructured":"T. M. Chan. A simple trapezoid sweep algorithm for reporting red\/blue segment intersections. In Proc. 6th Can. Conf. Comp. Geom., 1994."},{"key":"22_CR7","unstructured":"B. Chazelle. Triangulating a simple polygon in linear time. In Proc. IEEE Foundation of Comp. Sci., 1990."},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/147508.147511","volume":"39","author":"B. Chazelle","year":"1992","unstructured":"B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. JACM, 39:1\u201354, 1992.","journal-title":"JACM"},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01182771","volume":"11","author":"B. Chazelle","year":"1994","unstructured":"B. Chazelle, H. Edelsbrunner, L. J. Guibas, and M. Sharir. Algorithms for bichromatic line-segment problems and polyhedral terrains. Algorithmica, 11:116\u2013132, 1994.","journal-title":"Algorithmica"},{"key":"22_CR10","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle and L. J. Guibas. Fractional cascading: I. a data structuring technique. Algorithmica, 1:133\u2013162, 1986.","journal-title":"Algorithmica"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Y.-J. Chiang. Experiments on the practical I\/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep. In Proc of 4th Workshop on Algorithms and Data Structures, 1995.","DOI":"10.1007\/3-540-60220-8_75"},{"key":"22_CR12","unstructured":"Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-memory graph algorithms. In Proc. ACM-SIAM Symp. on Discrete Alg., pages 139\u2013149, Jan. 1995."},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"R. F. Cromp. An intellegent information fusion system for handling the archiving and querying of terabyte-sized spatial databases. In S. R. Tate ed., Report on the Workshop on Data and Image Compression Needs and Uses in the Scientific Community, CESDIS Technical Report Series, TR-93-99, pages 75\u201384, 1993.","DOI":"10.1063\/1.44469"},{"key":"22_CR14","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1016\/0196-6774(85)90030-6","volume":"6","author":"H. Edelsbrunner","year":"1985","unstructured":"H. Edelsbrunner and M. H. Overmars. Batched dynamic solutions to decomposable searching problems. Journal of Algorithms, 6:515\u2013542, 1985.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"22_CR15","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/357337.357341","volume":"3","author":"A. Fournier","year":"1984","unstructured":"A. Fournier and D. Y. Montuno. Triangulating simple polygons and equivalent problems. ACM Trans. on Graphics, 3(2):153\u2013174, 1984.","journal-title":"ACM Trans. on Graphics"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. External-memory computational geometry. In Proc. of IEEE Foundations of Comp. Sci., pages 714\u2013723, Nov. 1993.","DOI":"10.1109\/SFCS.1993.366816"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"L. M. Haas and W. F. Cody. Exploiting extensible dbms in integrated geographic information systems. In Proc. of Advances in Spatial Databases, LNCS 525, 1991.","DOI":"10.1007\/3-540-54414-3_50"},{"key":"22_CR18","series-title":"A.P.I.C. Series","volume-title":"Fundamentals of Spatial Information Systems.","author":"R. Laurini","year":"1992","unstructured":"R. Laurini and A. D. Thompson. Fundamentals of Spatial Information Systems. A.P.I.C. Series, Academic Press, New York, NY, 1992."},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"H. G. Mairson and J. Stolfi. Reporting and counting intersections between two sets of line segments. In R. Earnshaw (ed.), Theoretical Foundation of Computer Graphics and CAD, NATO ASI Series, Vol. F40, pages 307\u2013326, 1988.","DOI":"10.1007\/978-3-642-83539-1_11"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"M. H. Nodine and J. S. Vitter. Large-scale sorting in parallel memories. In Proc. of 3rd Annual ACM Symp. on Parallel Algorithms and Architectures, pages 29\u201339, July 1991.","DOI":"10.1145\/113379.113382"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"M. H. Nodine and J. S. Vitter. Deterministic distribution sort in shared and distributed memory multiprocessors. In Proc. 5th ACM Symp. on Parallel Algorithms and Architectures, pages 120\u2013129, June\u2013July 1993.","DOI":"10.1145\/165231.165247"},{"key":"22_CR22","first-page":"530","volume":"709","author":"L. Palazzi","year":"1993","unstructured":"L. Palazzi and J. Snoeyink. Counting and reporting red\/blue segment intersections. In Proc. of 3th Workshop on Algorithms and Data Structures, LNCS 709, pages 530\u2013540, 1993.","journal-title":"LNCS"},{"issue":"3","key":"22_CR23","first-page":"15","volume":"27","author":"Y. N. Patt","year":"1994","unstructured":"Y. N. Patt. The I\/O subsystem\u2014a candidate for improvement. Guest Editor's Introduction in IEEE Comp., 27(3):15\u201316, 1994.","journal-title":"Guest Editor's Introduction in IEEE Comp."},{"issue":"3","key":"22_CR24","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1109\/2.268881","volume":"27","author":"C. Ruemmler","year":"1994","unstructured":"C. Ruemmler and J. Wilkes. An introduction to disk drive modeling. IEEE Comp., 27(3): 17\u201328, Mar. 1994.","journal-title":"IEEE Comp."},{"key":"22_CR25","volume-title":"Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS","author":"H. Samet","year":"1989","unstructured":"H. Samet. Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison Wesley, MA, 1989."},{"key":"22_CR26","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0196-6774(82)90016-5","volume":"3","author":"V. K. Vaishnavi","year":"1982","unstructured":"V. K. Vaishnavi and D. Wood. Rectilinear line segment intersection, layered segment trees, and dynamization. Journal of Algorithms, 3:160\u2013176, 1982.","journal-title":"Journal of Algorithms"},{"key":"22_CR27","unstructured":"M. J. van Kreveld. Geographic information systems. Technical Report INF\/DOC-95-01, Utrecht University, 1995."},{"issue":"2\u20133","key":"22_CR28","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/BF01185207","volume":"12","author":"J. S. Vitter","year":"1994","unstructured":"J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory, I: Two-level memories. Algorithmica, 12(2\u20133):110\u2013147, 1994.","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '95"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60313-1_151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:00:18Z","timestamp":1742598018000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60313-1_151"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540603139","9783540449133"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-60313-1_151","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}