{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T17:07:17Z","timestamp":1742404037699},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662471"},{"type":"electronic","value":"9783540484820"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48482-5_17","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T08:23:24Z","timestamp":1187252604000},"page":"270-285","source":"Crossref","is-referenced-by-count":9,"title":["Algorithms for Performing Polygonal Map Overlay and Spatial Join on Massive Data Sets"],"prefix":"10.1007","author":[{"given":"Ludger","family":"Becker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Giesen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus H.","family":"Hinrichs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Vahrenhold","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,6,25]]},"reference":[{"unstructured":"P. Agarwal. Private communication. 1999.","key":"17_CR1"},{"unstructured":"D. Andrews, J. Snoeyink, J. Boritz, T. Chan, G. Denham, J. Harrison, and C. Zhu. Further comparison of algorithms for geometric intersection problems. In T. Waugh and R. Healey, editors, Advances in GIS Research \u2010 Proceedings of the 6th International Symposium on Spatial Data Handling (SDH\u201994), volume 2, 709\u2013724, 1994.","key":"17_CR2"},{"unstructured":"L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. Vitter. Scalable sweepingbased spatial join. In A. Gupta, O. Shmueli, and J. Widom, editors, VLDB\u201998: Proceedings of the 24th International Conference on Very Large Data Bases, 570\u2013581. Morgan Kaufmann, 1998.","key":"17_CR3"},{"doi-asserted-by":"crossref","unstructured":"I. Balaban. An optimal algorithm for finding segment intersections. In Proceedings of the 11th Annual ACM Symposium on Computational Geometry, 211\u2013219, 1995.","key":"17_CR4","DOI":"10.1145\/220279.220302"},{"unstructured":"U. Bartuschka, K. Mehlhorn, and S. N\u00e4her. A robust and eficient implementation of a sweep line algorithm for the straight line segment intersection problem. Online-Proccedings of the First Workshop on Algorithm Engineering < http:\/\/www.dsi.unive.it\/~wae97\/proceeedings\/ONLY_PAPERS\/pap13.ps.gz >, accessed 7 Jul. 1998, 1997.","key":"17_CR5"},{"issue":"9","key":"17_CR6","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"C-28","author":"J. Bentley","year":"1979","unstructured":"J. Bentley and T. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, C-28(9):643\u2013647, 1979.","journal-title":"IEEE Transactions on Computers"},{"doi-asserted-by":"crossref","unstructured":"T. Brinkho, H.-P. Kriegel, and B. Seeger. Eficient processing of spatial joins using R-trees. In P. Buneman and S. Jajoda, editors, Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, volume 22.2 of SIGMOD Record, 237\u2013246. ACM Press, June 1993.","key":"17_CR7","DOI":"10.1145\/170035.170075"},{"doi-asserted-by":"crossref","unstructured":"T. Brinkho, H.-P. Kriegel, R. Schneider, and B. Seeger. Multi-step processing of spatial joins. In R. Snodgrass and M. Winslett, editors, Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, volume 23.2 of SIGMOD Record, 197\u2013208. ACM Press, June 1994.","key":"17_CR8","DOI":"10.1145\/191839.191880"},{"unstructured":"A. Brinkmann and K. Hinrichs. Implementing exact line segment intersection in map overlay. In T. Poiker and N. Chrisman, editors, Proceedings of the Eighth International Symposium on Spatial Data Handling, pages 569\u2013579. International Geographic Union, Geographic Information Science Study Group, 1998.","key":"17_CR9"},{"issue":"2","key":"17_CR10","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1109\/TC.1981.6312179","volume":"C-30","author":"K. Brown","year":"1981","unstructured":"K. Brown. Comments on \u201cAlgorithms for reporting and counting geometric intersections\u201d. IEEE Transactions on Computers, C-30(2):147\u2013148, 1981.","journal-title":"IEEE Transactions on Computers"},{"key":"17_CR11","series-title":"Lect Notes Comput Sci","first-page":"69","volume-title":"Advances in Spatial Databases \u2014Proceedings of the Fifth International Symposium on Spatial Databases (SSD\u2019 97)","author":"E. Chan","year":"1997","unstructured":"E. Chan and J. Ng. A general and eficient implementation of geometric operators and predicates. In M. Scholl and A. Voisard, editors, Advances in Spatial Databases \u2014Proceedings of the Fifth International Symposium on Spatial Databases (SSD\u2019 97), volume 1262 of Lecture Notes in Computer Science, 69\u201393. Springer, 1997."},{"unstructured":"T. Chan. A simple trapezoid sweep algorithm for reporting red\/blue segment intersections. In Proceedings of the 6th Canadian Conference on Computational Geometry, 263\u2013268, 1994.","key":"17_CR12"},{"issue":"1","key":"17_CR13","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. Journal of the ACM, 39(1):1\u201354, 1992.","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer, Berlin, 1997.","key":"17_CR14","DOI":"10.1007\/978-3-662-03427-9"},{"unstructured":"Environmental Systems Research Institute, Inc. ARC\/INFO, the world\u2019s GIS. ESRI White Paper Series, Redlands, CA, March 1995.","key":"17_CR15"},{"key":"17_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/3-540-60159-7_3","volume-title":"Advances in Spatial Databases \u2014 Proceedings of the Fourth International Symposium on Spatial Databases (SSD\u2019 95)","author":"U. Finke","year":"1995","unstructured":"U. Finke and K. Hinrichs. The quad view data structure: a representation for planar subdivisions. In M. Egenhofer and J. Herring, editors, Advances in Spatial Databases \u2014 Proceedings of the Fourth International Symposium on Spatial Databases (SSD\u2019 95), volume 951 of Lecture Notes in Computer Science, 29\u201346, 1995."},{"key":"17_CR17","first-page":"230","volume":"2","author":"W. Franklin","year":"1983","unstructured":"W. Franklin. Adaptive grids for geometric operations. In Proceedings of the Sixth International Symposium on Automated Cartography (Auto-Carto Six), volume 2, 230\u2013239, 1983.","journal-title":"Proceedings of the Sixth International Symposium on Automated Cartography (Auto-Carto Six)"},{"unstructured":"A. Giesen. Verschneidung von Regionen in Geographischen Informationssystemen (Overlaying polygonal regions in geographic information systems). Master\u2019s thesis, University of M\u00fcnster, Dept. of Computer Science, November 1998. (in German).","key":"17_CR18"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(87)90018-1","volume":"42","author":"R. G\u00fcting","year":"1987","unstructured":"R. G\u00fcting and W. Schilling. A practical divide-and conquer algorithm for the rectangle intersection problem. Information Sciences, 42:95\u2013112, 1987.","journal-title":"Information Sciences"},{"key":"17_CR20","series-title":"Lect Notes Comput Sci","first-page":"165","volume-title":"Advances in Spatial Databases \u2014 Proceedings of the Fifth International Symposium on Spatial Databases (SSD\u2019 97","author":"Y.-W. Huang","year":"1997","unstructured":"Y.-W. Huang, M. Jones, and E. Rundensteiner. Improving spatial intersect using symbolic intersect detection. In M. Scholl and A. Voisard, editors, Advances in Spatial Databases \u2014 Proceedings of the Fifth International Symposium on Spatial Databases (SSD\u2019 97), volume 1262 of Lecture Notes in Computer Science, 165\u2013177. Springer, 1997."},{"doi-asserted-by":"crossref","unstructured":"H.-P. Kriegel, T. Brinkho, and R. Schneider. An eficient map overlay algorithm based on spatial access methods and computational geometry. In Proceedings of the International Workshop on DBMS\u2019s for Geographic Applications, 194\u2013211, Capri, May 12\u201317 1991.","key":"17_CR21","DOI":"10.1007\/978-3-642-77605-2_11"},{"doi-asserted-by":"crossref","unstructured":"M.-L. Lo and C. Ravishankar. Spatial joins using seeded trees. In R. Snodgrass and M. Winslett, editors, Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, volume 23.2 of SIGMOD Record, 209\u2013220. ACM Press, June 1994.","key":"17_CR22","DOI":"10.1145\/191839.191881"},{"doi-asserted-by":"crossref","unstructured":"H. Mairson and J. Stolfi. Reporting and counting intersections between two sets of line segments. In R. Earnshaw, editor, Theoretical Foundations of Computer Graphics and CAD, volume F40 of NATO ASI, 307\u2013325. Springer-Verlag, 1988.","key":"17_CR23","DOI":"10.1007\/978-3-642-83539-1_11"},{"issue":"10","key":"17_CR24","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1145\/358656.358681","volume":"25","author":"J. Nievergelt","year":"1982","unstructured":"J. Nievergelt and F. Preparata. Plane-sweep algorithms for intersecting geometric figures. Communications of the ACM, 25(10):739\u2013747, 1982.","journal-title":"Communications of the ACM"},{"doi-asserted-by":"crossref","unstructured":"J. Orenstein. A comparison of spatial query processing techniques for native and parameter spaces. In H. Garcia-Molina and H. Jagadish, editors. Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, volume 19.2 of SIGMOD Record, pages 343\u2013352. ACM Press, June 1990.","key":"17_CR25","DOI":"10.1145\/93597.98743"},{"key":"17_CR26","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0734-189X(86)90046-0","volume":"34","author":"T. Ottmann","year":"1986","unstructured":"T. Ottmann and D. Wood. Space-economical plane-sweep algorithms. Computer Vision, Graphics and Image Processing, 34:35\u201351, 1986.","journal-title":"Computer Vision, Graphics and Image Processing"},{"issue":"3","key":"17_CR27","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1137\/0220029","volume":"20","author":"J. Pach","year":"1991","unstructured":"J. Pach and M. Sharir. On vertical visibility in arrangements of segments and the queue size in the Bentley-Ottmann line sweeping algorithm. SIAM Journal on Computing, 20(3):460\u2013470, 1991.","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"J. Patel and D. DeWitt. Partition based spatial-merge join. In H. Jagadish and I. Mumick, editors, Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, volume 25.2 of SIGMOD Record, 259\u2013270. ACM Press, June 1996.","key":"17_CR28","DOI":"10.1145\/233269.233338"},{"unstructured":"F. Preparata and M. Shamos. Computational Geometry: An Introduction. Springer, Berlin, 2nd edition, 1988.","key":"17_CR29"},{"key":"17_CR30","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M. Sharir","year":"1995","unstructured":"M. Sharir and P. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge, 1995."},{"doi-asserted-by":"crossref","unstructured":"J. Vitter. External memory algorithms. In Proceedings of the 17th Annual ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS\u2019 98), 119\u2013128, 1998. invited tutorial.","key":"17_CR31","DOI":"10.1145\/275487.275501"}],"container-title":["Lecture Notes in Computer Science","Advances in Spatial Databases"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48482-5_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T00:38:20Z","timestamp":1556757500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48482-5_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662471","9783540484820"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-48482-5_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}