Bentley–Ottmann algorithm: Difference between revisions

Revision as of 11:34, 20 May 2018

Latest revision as of 07:06, 20 August 2025

(17 intermediate revisions by 9 users not shown)

Line 1:

{{short description|Sweep line algorithm}}

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 {{examplesharvtxt|date=MarchChazelle|Edelsbrunner|1992}} 2018and {{harvtxt|Balaban|1995}}, the Bentley–Ottmann algorithm remains a practical choice due to its simplicity and low memory requirements{{citation needed|reason=Link to robutsrobust implementatinosimplementations, such as CGAL one, required.|date=March 2018}}.

==Overall strategy==

Line 28 ⟶ 29:

The algorithm does not need to maintain explicitly a representation of the sweep line ''L'' or its position in the plane. Rather, the position of ''L'' is represented indirectly: it is the vertical line through the point associated with the most recently processed event.

The binary search tree may be any [[Self-balancing binary search tree|balanced binary search tree]] data structure, such as a [[red-blackred–black tree]]; all that is required is that insertions, deletions, and searches take logarithmic time. Similarly, the priority queue may be a [[binary heap]] or any other logarithmic-time priority queue; more sophisticated priority queues such as a [[Fibonacci heap]] are not necessary. Note that the space complexity of the priority queue depends on the data structure used to implement it.

==Detailed algorithm==

Line 35 ⟶ 36:

#Initialize a [[self-balancing binary search tree]] ''T'' of the line segments that cross the sweep line ''L'', ordered by the ''y''-coordinates of the crossing points. Initially, ''T'' is empty. (Even though the line sweep ''L'' is not explicitly represented, it may be helpful to imagine it as a vertical line which, initially, is at the left of all input segments.)

#While ''Q'' is nonempty, find and remove the event from ''Q'' associated with a point ''p'' with minimum ''x''-coordinate. Determine what type of event this is and process it according to the following case analysis:

#*If ''p'' is the left endpoint of a line segment ''s'', insert ''s'' into ''T''. Find the line-segments ''r'' and ''t'' that are respectively immediately belowabove and abovebelow ''s'' in ''T'' (if they exist); if theirthe crossing of ''r'' and ''t'' (the neighbours of ''s'' in the status data structure) forms a potential future event in the event queue, remove itthis possible future event from the event queue. If ''s'' crosses ''r'' or ''t'', add those crossing points as potential future events in the event queue.

#*If ''p'' is the right endpoint of a line segment ''s'', remove ''s'' from ''T''. Find the segments ''r'' and ''t'' that (prior to the removal of ''s'') were respectively immediately above and below it in ''T'' (if they exist). If ''r'' and ''t'' cross, add that crossing point as a potential future event in the event queue.

#*If ''p'' is the crossing point of two segments ''s'' and ''t'' (with ''s'' below ''t'' to the left of the crossing), swap the positions of ''s'' and ''t'' in ''T''. FindAfter the swap, find the segments ''r'' and ''u'' (if they exist) that are immediately below and above ''t'' and ''s'', respectively (after the swap). Remove any crossing points ''rs'' (i.e. a crossing point between ''r'' and ''s'') and ''tu'' (i.e. a crossing point between ''t'' and ''u'') from the event queue, and, if ''r'' and ''t'' cross or ''s'' and ''u'' cross, add those crossing points to the event queue.

==Analysis==

Line 69 ⟶ 70:

==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|s2cid=6342118|doi-access=free|isbn=0-89791-724-3 }}.

*{{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|editor1-link=Giuseppe F. Italiano|editor2-first=S.|editor2-last=Orlando|access-date=2009-05-27|archive-date=2017-06-06|archive-url=https://web.archive.org/web/20170606120507/http://www.dsi.unive.it/~wae97/proceedings/|url-status=dead}}.

*{{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|s2cid=1618521}}.

*{{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=[https://archive.org/details/computationalgeo00berg/page/19 19–44]|chapter-url-access=registration|chapter-url=https://archive.org/details/computationalgeo00berg/page/19}}.

*{{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=httphttps://www.cs.brown.edu/research/pubs/pdfs/2000/Boissonnat-2000-RPS.pdf|doi=10.1137/S0097539797329373|volume=29|issue=5|pages=1401–1421}}.

*{{citation|last=Brown|first=K. Q.|title=Comments on "Algorithms for Reporting and Counting Geometric Intersections"|journal=IEEE Transactions on Computers|year=1981|volume=C-30|issue=2|page=147|doi=10.1109/tc.1981.6312179|s2cid=206622367}}.

*{{citation|last1=Chazelle|first1=Bernard|author1-link=Bernard Chazelle|last2=Edelsbrunner|first2=Herbert|author2-link=Herbert Edelsbrunner|title=An optimal algorithm for intersecting line segments in the plane|journal=[[Journal of the ACM]]|volume=39|issue=1|pages=1–54|year=1992|doi=10.1145/147508.147511|s2cid=785741|doi-access=free}}.

*{{citation|last1=Chen|first1=E. Y.|last2=Chan|first2=T. M.|author2-link=Timothy M. Chan|contribution=A space-efficient algorithm for segment intersection|title=Proc. 15th Canadian Conference on Computational Geometry|year=2003|url=http://www.cccg.ca/proceedings/2003/31.pdf}}.

*{{citation|last=Clarkson|first=K. L.|authorlink=Kenneth L. Clarkson|contribution=Applications of random sampling in computational geometry, II|title=Proc. 4th ACM Symp. Computational Geometry|pages=1–11|year=1988|doi=10.1145/73393.73394|s2cid=15134654|doi-access=free|isbn=0-89791-270-5 }}.

*{{citation|last1=Clarkson|first1=K. L.|author1-link=Kenneth L. Clarkson|last2=Cole|first2=R.|last3=Tarjan|first3=R. E.|author3-link=Robert Tarjan|title=Randomized parallel algorithms for trapezoidal diagrams|journal=[[International Journal of Computational Geometry and Applications]]|volume=2|issue=2|year=1992|pages=117–133|doi=10.1142/S0218195992000081}}. Corrigendum, '''2''' (3): 341–343.

*{{citation|last1=Eppstein|first1=D.|author1-link=David Eppstein|last2=Goodrich|first2=M. |author2-link=Michael T. Goodrich|last3=Strash|first3=D.|contribution=Linear-time algorithms for geometric graphs with sublinearly many crossings|title=Proc. 20th ACM-SIAM Symp. Discrete Algorithms (SODA 2009)|year=2009|pages=150–159|doi=10.1137/090759112|arxiv=0812.0893|bibcode=2008arXiv0812.0893E|s2cid=13044724}}.

*{{citation|last=Mulmuley|first=K.|authorlink=Ketan Mulmuley|contribution=A fast planar partition algorithm, I|title=[[Symposium on Foundations of Computer Science|Proc. 29th IEEE Symp. Foundations of Computer Science (FOCS 1988)]]|year=1988|pages=580–589|doi=10.1109/SFCS.1988.21974|isbn=0-8186-0877-3 |s2cid=34582594}}.

*{{citation|last=O'Rourke|first=J.|authorlink= Joseph O'Rourke (professor)|title=Computational Geometry in C|edition=2nd|publisher=Cambridge University Press|year=1998|isbn=978-0-521-64976-6|chapter=Section 7.7: Intersection of segments|pages=263–265}}.

*{{citation|last1=Preparata|first1=F. P.|author1-link=Franco P. Preparata|last2=Shamos|first2=M. I.|author2-link=Michael Ian Shamos|title=Computational Geometry: An Introduction|publisher=Springer-Verlag|year=1985|chapter=Section 7.2.3: Intersection of line segments|pages=278–287|bibcode=1985cgai.book.....P}}.

*{{citation|last1=Pach|first1=J.|author1-link=János Pach|last2=Sharir|first2=M.|author2-link=Micha Sharir|title=On vertical visibility in arrangements of segments and the queue size in the Bentley–Ottmann line sweeping algorithm|journal=SIAM Journal on Computing|volume=20|year=1991|pages=460–470|issue=3|doi=10.1137/0220029|mr=1094525}}.

*{{citation|last1=Shamos|first1=M. I.|author1-link=Michael Ian Shamos|contribution=Geometric intersection problems|title=[[Symposium on Foundations of Computer Science|17th IEEE Conf. Foundations of Computer Science (FOCS 1976)]]|pages=208–215|year=1976|doi=10.1109/SFCS.1976.16|last2=Hoey|first2=Dan|s2cid=124804}}.

==External links==