Bentley–Ottmann algorithm: Difference between revisions

Revision as of 01:37, 8 October 2015

Revision as of 07:15, 25 November 2015

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>{{Citesfnp|Shamos|Hoey|1976}} journala 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''² / log ''n''), this is an improvement on a naïve algorithm that tests every pair of segments, which takes O(''n''²).

| 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''² / log ''n''), this is an improvement on a naïve algorithm that tests every pair of segments, which takes O(''n''²).

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.

Line 59 ⟶ 50:

*Define a line segment to be a [[closed set]], containing its endpoints. Therefore, two line segments that share an endpoint, or a line segment that contains an endpoint of another segment, both count as an intersection of two line segments.

*When multiple line segments intersect at the same point, create and process a single event point for that intersection. The updates to the binary search tree caused by this event may involve removing any line segments for which this is the right endpoint, inserting new line segments for which this is the left endpoint, and reversing the order of the remaining line segments containing this event point. The output from the version of the algorithm described by {{harvtxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2000}} consists of the set of intersection points of line segments, labeled by the segments they belong to, rather than the set of pairs of line segments that intersect.

A similar approach to degeneracies was used in the [[Library of Efficient Data types and Algorithms|LEDA]] implementation of the Bentley–Ottmann algorithm.<ref name="LEDA">{{harvtxt|Bartuschka|Mehlhorn|NáherNäher|1997}}.</ref>

For the correctness of the algorithm, it is necessary to determine without approximation the above-below relations between a line segment endpoint and other line segments, and to correctly prioritize different event points. For this reason it is standard to use integer coordinates for the endpoints of the input line segments, and to represent the [[rational number]] coordinates of the intersection points of two segments exactly, using [[arbitrary-precision arithmetic]]. However, it may be possible to speed up the calculations and comparisons of these coordinates by using [[floating point]] calculations and testing whether the values calculated in this way are sufficiently far from zero that they may be used without any possibility of error.<ref name="LEDA"/> The exact arithmetic calculations required by a naïve implementation of the Bentley–Ottmann algorithm may require five times as many bits of precision as the input coordinates, but {{harvtxt|Boissonat|Preparata|2000}} describe modifications to the algorithm that reduce the needed amount of precision to twice the number of bits as the input coordinates.

Line 73 ⟶ 64:

==References==

*{{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|titleurl=[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|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}}.