Content deleted Content added
Citation bot (talk | contribs) Added isbn. | Use this bot. Report bugs. | Suggested by Abductive | Category:Computational geometry | #UCB_Category 60/76 |
m →References: HTTP to HTTPS for Brown University |
||
| (One intermediate revision by one other user not shown) | |||
Line 2:
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
==Overall strategy==
Line 74:
*{{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=
*{{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}}.
| |||