Bentley–Ottmann algorithm: Difference between revisions

Revision as of 15:39, 26 January 2018

Revision as of 16:37, 5 March 2018

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 ''<math>n''</math> line segments with ''<math>k''</math> crossings, the Bentley–Ottmann algorithm takes time <math>\mathcal{O}((''n'' + ''k'') \log ''n'')</math>. In cases where ''<math>k'' = \mathcal{o}\left(''\frac{n''^{^2} / }{\log ''n''} \right)</math>, this is an improvement on a naïve algorithm that tests every pair of segments, which takes Θ(''n''<supmath>\Theta(n^2)</supmath>).

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–Ottmann algorithm remains a practical choice due to its simplicity and low memory requirements.