Bentley–Ottmann algorithm: Difference between revisions

Revision as of 12:26, 3 February 2023

Revision as of 06:50, 11 March 2024

Line 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}}.

Line 78:

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