{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:39Z","timestamp":1787337579823,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>In this paper, we reexamine in the framework of robust computation the Bentley--Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being very sensitive to numerical errors. Indeed, a simple analysis reveals that it involves predicates of degree 5, presumably never evaluated exactly in most implementations. Within the exact-computation paradigm we introduce two models of computation aimed at replacing the conventional model of real-number arithmetic. The first model (predicate arithmetic) assumes the exact evaluation of the signs of algebraic expressions of some degree, and the second model (exact arithmetic) assumes the exact computation of the value of such (bounded-degree) expressions. We identify the characteristic geometric property enabling the correct report of all intersections by plane sweeps. Verification of this property involves only predicates of (optimal) degree 2, but its straightforward implementation appears highly inefficient. We then present algorithmic variants that have low degree under these models and achieve the same performance as the original Bentley--Ottmann algorithm. The technique is applicable to a more general case of curved segments.<\/jats:p>","DOI":"10.1137\/s0097539797329373","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1401-1421","source":"Crossref","is-referenced-by-count":35,"title":["Robust Plane Sweep for Intersecting Segments"],"prefix":"10.1137","volume":"29","author":[{"given":"Jean-Daniel","family":"Boissonnat","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Franco P.","family":"Preparata","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"I. J. Balaban,\n                      An optimal algorithm for finding segment intersections\n                      , in Proceedings of the 11th Annual ACM Symposium on Computational Geometry, Vancouver, Canada, 1995, pp. 211\u2013219.","DOI":"10.1145\/220279.220302"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8702-0"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"H. Br\u00f6nnimann, I. Emiris, V. Pan, and S. Pion,\n                      Computing exact geometric predicates using modular arithmetic with single precision\n                      , in Proceedings of the 13th Annual ACM Symposium on Computational Geometry, Nice, France, 1997, pp. 174\u2013182.","DOI":"10.1145\/262839.262948"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010003"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.6312179"},{"key":"R7","unstructured":"C. Burnikel,\n                      Exact Computation of Voronoi Diagrams and Line Segment Intersections\n                      , Ph.D. thesis, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, Germany, 1996."},{"key":"R8","unstructured":"95]bkmnsu\u2010egcl\u201095 C. Burnikel, J. K\u00f6nnemann, K. Mehlhorn, S. N\u00e4her, S. Schirra, and C. Uhrig,\n                      Exact geometric computation in LEDA\n                      , in Proceedings of the 11th Annual ACM Symposium on Computational Geometry, Vancouver, Canada, 1995, pp. C18\u2013C19."},{"key":"R9","unstructured":"Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra, On degeneracy in geometric computations, ACM, New York, 1994, 16\u20132395d:68145"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574703"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/147508.147511"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01182771"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson,\n                      Safe and effective determinant evaluation\n                      , !in Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1992, pp. 387\u2013395.","DOI":"10.1109\/SFCS.1992.267751"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90038-X"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. R. Forrest,\n                      Computational geometry in practice\n                      , in Fundamental Algorithms for Computer Graphics, NATO Adv. Sci. Inst. Ser. F Comput. Systems Sci. 17, R. A. Earnshaw, ed., Springer\u2010Verlag, Berlin, 1985, pp. 707\u2013724.","DOI":"10.1007\/978-3-642-84574-1_30"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"A. R. Forrest,\n                      Computational geometry and software engineering: Towards a geometric computing environment\n                      , in Techniques for Computer Graphics, D. F. Rogers and R. A. Earnshaw, eds., Springer\u2010Verlag, Berlin, 1987, pp. 23\u201337.","DOI":"10.1007\/978-1-4613-8713-8_4"},{"key":"R18","unstructured":"S. Fortune,\n                      Progress in computational geometry\n                      , in Directions in Computational Geometry, R. Martin, ed., Information Geometers, Winchester, UK, 1993, pp. 81\u2013128."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"S. Fortune and C. J. Van Wyk,\n                      Efficient exact arithmetic for computational geometry\n                      , in Proceedings of the 9th Annual ACM Symposium on Computational Geometry, San Diego, CA, 1993, pp. 163\u2013172.","DOI":"10.1145\/160985.161015"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/103162.103163"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187878"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"John Hershberger, Subhash Suri, Applications of a semi\u2010dynamic convex hull algorithm, Lecture Notes in Comput. Sci., Vol. 447, Springer, Berlin, 1990, 380\u20133921076038","DOI":"10.1007\/3-540-52846-6_106"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0054"},{"key":"R24","unstructured":"J. Hobby,\n                      Practical Segment Intersection with Finite Precision Output\n                      , Technical Report 93\/2\u201027, Bell Laboratories, Murray Hill, NJ, 1993."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/2.16223"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1109\/38.41469"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796305365"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"H. G. Mairson and J. Stolfi,\n                      Reporting and counting intersections between two sets of line segments\n                      , in Theoretical Foundations of Computer Graphics and CAD, NATO Adv. Sci. Inst. Ser. F. Comput. Systems Sci. 40, R. A. Earnshaw, ed., Springer\u2010Verlag, Berlin, 1988, pp. 307\u2013325.","DOI":"10.1007\/978-3-642-83539-1_11"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(88)90061-6"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"V. Milenkovic,\n                      Double precision geometry: A general technique for calculating line and segment intersections using rounded arithmetic\n                      , in Proceedings of the 30th Annual IEEE Symposium on Foundations Computer Science, IEEE Computer Society, Los Alamitos, CA, 1989, pp. 500\u2013505.","DOI":"10.1109\/SFCS.1989.63525"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1137\/0214046"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1145\/358656.358681"},{"key":"R33","unstructured":"D. Priest,\n                      On Properties of Floating Point Arithmetics: Numerical Stability and the Cost of Accurate Computations\n                      , Ph.D. thesis, Dept. of Mathematics, Univ. of California at Berkeley, 1992."},{"key":"R34","unstructured":"P. Schorn,\n                      Robust Algorithms in a Program Library for Geometric Computation\n                      , volume 32 of Informatik\u2010Dissertationen ETH Z\u00fcrich, Verlag der Fachvereine, Z\u00fcrich, Switzerland, 1991."},{"key":"R35","doi-asserted-by":"crossref","unstructured":"J. R. Shewchuk,\n                      Robust adaptive floating\u2010point geometric predicates\n                      , in Proceedings of the 12th Annual ACM Symposium on Computational Geometry, Philadelphia, PA, 1996, pp. 141\u2013150.","DOI":"10.1145\/237218.237337"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00040-2"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539797329373","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:28Z","timestamp":1787336308000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539797329373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S0097539797329373"],"URL":"https:\/\/doi.org\/10.1137\/s0097539797329373","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}