Content deleted Content added
Magioladitis (talk | contribs) |
added ref to shamos hoey algorithim |
||
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]]<ref>{{Cite journal
| doi = 10.1109/SFCS.1976.16 | url = http://euro.ecom.cmu.edu/people/faculty/mshamos/1976GeometricIntersection.pdf | chapter = Geometric intersection problems | title = 17th Annual Symposium on Foundations of Computer Science (sfcs 1976) | pages = 208 | year = 1976 | last1 = Shamos | first1 = M. I. | last2 = Hoey | first2 = D. }}</ref>, 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|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.
| |||