Content deleted Content added
m fix ref errors |
mNo edit summary |
||
Line 1:
In [[computational geometry]], the '''Bentley–Ottmann algorithm''' is a [[sweep line algorithm]] for listing all [[line segment intersection|crossings in a set of line segments]]. It extends the [[Shamos–Hoey algorithm]],{{sfnp|Shamos|Hoey|1976}} a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of ''n'' line segments with ''k'' crossings, the Bentley–Ottmann algorithm takes time O((''n'' + ''k'') log ''n''). In cases where ''k'' = o(''n''<sup>2</sup> / log ''n''), this is an improvement on a naïve algorithm that tests every pair of segments, which takes O(''n''<sup>2</sup>).
The algorithm was initially developed by {{harvs|first1=Jon|last1=Bentley|author1-link=Jon Bentley (computer scientist)|first2=Thomas|last2=Ottmann|year=1979|txt}}; it is described in more detail in the textbooks {{harvtxt|Preparata|Shamos|1985}}, {{harvtxt|O'Rourke|1998}}, and {{harvtxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2000}}. Although [[asymptotic analysis|asymptotically]] faster algorithms are now known, the Bentley–Ottman algorithm remains a practical choice due to its simplicity and low memory requirements.
==Overall strategy==
Line 65:
*{{citation|last=Balaban|first=I. J.|contribution=An optimal algorithm for finding segments intersections|title=Proc. 11th ACM Symp. Computational Geometry|year=1995|pages=211–219|doi=10.1145/220279.220302}}.
*{{citation|last1=Bartuschka|first1=U.|last2=Mehlhorn|first2=K.|author2-link=Kurt Mehlhorn|last3=Näher|first3=S.|contribution=A robust and efficient implementation of a sweep line algorithm for the straight line segment intersection problem|url=http://www.dsi.unive.it/~wae97/proceedings/|title=Proc. Worksh. Algorithm Engineering|year=1997|contribution-url=http://www.dsi.unive.it/~wae97/proceedings/ONLY_PAPERS/pap13.ps.gz|editor1-first=G. F.|editor1-last=Italiano|editor2-first=S.|editor2-last=Orlando}}.
*{{citation|last1=Bentley|first1=J. L.|author1-link=Jon Bentley (computer scientist)|last2=Ottmann|first2=T. A.|title=Algorithms for reporting and counting geometric intersections|journal=IEEE Transactions on Computers|volume=C-28|issue=9|pages=643–647|year=1979|doi=10.1109/TC.1979.1675432}}.
*{{citation|last1=de Berg|first1=Mark|last2=van Kreveld|first2=Marc|last3=Overmars|first3=Mark|author3-link=Mark Overmars|last4=Schwarzkopf|first4=Otfried|title=Computational Geometry|publisher=Springer-Verlag|year=2000|isbn=978-3-540-65620-3|edition=2nd|chapter=Chapter 2: Line segment intersection|pages=19–44}}.
*{{citation|last1=Boissonat|first1=J.-D.|last2=Preparata|first2=F. P.|author2-link=Franco P. Preparata|title=Robust plane sweep for intersecting segments|journal=SIAM Journal on Computing|year=2000|url=http://www.cs.brown.edu/research/pubs/pdfs/2000/Boissonnat-2000-RPS.pdf|doi=10.1137/S0097539797329373|volume=29|issue=5|pages=1401–1421}}.
| |||