{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:59:51Z","timestamp":1725494391349},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540423065"},{"type":"electronic","value":"9783540477389"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-47738-1_23","type":"book-chapter","created":{"date-parts":[[2007,11,6]],"date-time":"2007-11-06T17:52:49Z","timestamp":1194371569000},"page":"244-251","source":"Crossref","is-referenced-by-count":4,"title":["Intersecting Red and Blue Line Segments in Optimal Time and Precision"],"prefix":"10.1007","author":[{"given":"Andrea","family":"Mantler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jack","family":"Snoeyink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,9,20]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Ivan J. Balaban. An optimal algorithm for finding segment intersections. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 211\u2013219, 1995.","DOI":"10.1145\/220279.220302"},{"key":"23_CR2","unstructured":"U. Bartuschka, K. Mehlhorn, and S. N\u00e4her. A robust and efficient implementation of a sweep line algorithm for the straight line segment intersection problem. In Proc. Workshop on Algorithm Engineering, pages 124\u2013135, 1997."},{"issue":"9","key":"23_CR3","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"C-28","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput., C-28(9):643\u2013647, September 1979.","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"23_CR4","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1109\/38.67707","volume":"11","author":"J. F. Blinn","year":"1991","unstructured":"J. F. Blinn. A trip down the graphics pipeline: Line clipping. IEEE Comput. Graph. Appl., 11(1):98\u2013105, 1991.","journal-title":"IEEE Comput. Graph. Appl."},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"J.-D. Boissonnat and J. Snoeyink. Efficient algorithms for line and curve segment intersection using restricted predicates. In Proc. 15th Annu. ACM Sympos. Comput. Geom., pages 370\u2013379, 1999.","DOI":"10.1145\/304893.304991"},{"issue":"5","key":"23_CR6","doi-asserted-by":"publisher","first-page":"1401","DOI":"10.1137\/S0097539797329373","volume":"29","author":"J.-D. Boissonnat","year":"2000","unstructured":"Jean-Daniel Boissonnat and Franco P. Preparata. Robust plane sweep for intersecting segments. SIAM J. Comp., 29(5):1401\u20131421, 2000.","journal-title":"SIAM J. Comp."},{"key":"23_CR7","unstructured":"Andreas Brinkmann and Klaus Hinrichs. Implementing exact line segment intersection in map overlay. In Proc. 8th Intl. Symp. Spatial Data Handling, pages 569\u2013579. International Geographical Union, 1998."},{"key":"23_CR8","unstructured":"T. M. Chan. A simple trapezoid sweep algorithm for reporting red\/blue segment intersections. In Proc. 6th Canad. Conf. Comput. Geom., pages 263\u2013268, 1994."},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(86)90025-5","volume":"32","author":"B. Chazelle","year":"1986","unstructured":"Bernard Chazelle. Reporting and counting segment intersections. J. Comput. Syst. Sci., 32:156\u2013182, 1986.","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"23_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/147508.147511","volume":"39","author":"B. Chazelle","year":"1992","unstructured":"Bernard Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. J. ACM, 39(1):1\u201354, 1992.","journal-title":"J. ACM"},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01182771","volume":"11","author":"B. Chazelle","year":"1994","unstructured":"Bernard Chazelle, H. Edelsbrunner, Leonidas J. Guibas, and Micha Sharir. Algorithms for bichromatic line segment problems and polyhedral terrains. Algorithmica, 11:116\u2013132, 1994.","journal-title":"Algorithmica"},{"key":"23_CR12","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1142\/S0218195996000307","volume":"6","author":"O. Devillers","year":"1996","unstructured":"Olivier Devillers and Andreas Fabri. Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers. Internat. J. Comput. Geom. Appl., 6:487\u2013506, 1996.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"J. R. Driscoll","year":"1989","unstructured":"J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan. Making data structures persistent. J. Comput. Syst. Sci., 38:86\u2013124, 1989.","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"M. Goodrich, L. J. Guibas, J. Hershberger, and P. Tanenbaum. Snap rounding line segments efficiently in two and three dimensions. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 284\u2013293, 1997.","DOI":"10.1145\/262839.262985"},{"key":"23_CR15","volume-title":"Data Structures and Algorithms in Java","author":"M. T. Goodrich","year":"1998","unstructured":"Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java. John Wiley & Sons, New York, NY, 1998."},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1142\/S0218195998000096","volume":"8","author":"L. Guibas","year":"1998","unstructured":"Leonidas Guibas and David Marimont. Rounding arrangements dynamically. Internat. J. Comput. Geom. Appl., 8:157\u2013176, 1998.","journal-title":"Internat. J. Comput. Geom. Appl."},{"issue":"4","key":"23_CR17","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0925-7721(99)00021-8","volume":"13","author":"J. D. Hobby","year":"1999","unstructured":"J. D. Hobby. Practical segment intersection with finite precision output. Comput. Geom. Theory Appl., 13(4):199\u2013214, October 1999.","journal-title":"Comput. Geom. Theory Appl."},{"key":"23_CR18","series-title":"NATO ASI Series F","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/978-3-642-83539-1_11","volume-title":"Theoretical Foundations of Computer Graphics and CAD","author":"H. G. Mairson","year":"1988","unstructured":"H. G. Mairson and J. Stolfi. Reporting and counting intersections between two sets of line segments. In R. A. Earnshaw, editor, Theoretical Foundations of Computer Graphics and CAD, volume 40 of NATO ASI Series F, pages 307\u2013325. Springer-Verlag, Berlin, West Germany, 1988."},{"key":"23_CR19","unstructured":"Victor J. Milenkovic. Practical methods for set operations on polygons using exact arithmetic. In Proc. 7th Canad. Conf. Comput. Geom., pages 55\u201360, 1995."},{"key":"23_CR20","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF02187877","volume":"2","author":"D. M. Mount","year":"1987","unstructured":"D. M. Mount. Storing the subdivision of a polyhedral surface. Discrete Comput. Geom., 2:153\u2013174, 1987.","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"23_CR21","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1006\/cgip.1994.1027","volume":"56","author":"L. Palazzi","year":"1994","unstructured":"L. Palazzi and J. Snoeyink. Counting and reporting red\/blue segment intersections. CVGIP: Graph. Models Image Process., 56(4):304\u2013311, 1994.","journal-title":"CVGIP: Graph. Models Image Process."},{"issue":"3","key":"23_CR22","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. D. Sleator","year":"1983","unstructured":"D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362\u2013381, 1983.","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR23","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0010-4485(80)90025-1","volume":"12","author":"R. B. Tilove","year":"1980","unstructured":"R. B. Tilove and A. A. G. Requicha. Closure of boolean operations on geometric entities. Comput. Aided Design, 12:219\u2013220, 1980.","journal-title":"Comput. Aided Design"}],"container-title":["Lecture Notes in Computer Science","Discrete and Computational Geometry"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-47738-1_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T02:19:19Z","timestamp":1556936359000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-47738-1_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540423065","9783540477389"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-47738-1_23","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}