Content deleted Content added
Add reference |
Add reference |
||
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]], i.e. it finds the ''intersection points'' (or, simply, ''intersections'') 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 (or intersections), 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 <math>\Theta(n^2)</math>.
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 by {{harvtxt|Chazelle|Edelsbrunner|1992}} and {{harvtxt|Balaban|1995}}, the Bentley–Ottmann algorithm remains a practical choice due to its simplicity and low memory requirements{{citation needed|reason=Link to robuts implementatinos, such as CGAL one, required.|date=March 2018}}.
==Overall strategy==
| |||