Bentley–Ottmann algorithm

In <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a>, the Bentley–Ottmann algorithm is a <a href="/facts/Sweep_line_algorithm/phUJCw6U">sweep line algorithm</a> for listing all <a href="/facts/Line_segment_intersection/RwH57yPq">crossings in a set of line segments</a>, i.e. it finds the intersection points (or, simply, intersections) of line segments. It extends the Shamos–Hoey algorithm, a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of 
 
 
 
 n
 
 
 {\displaystyle n}
 
 line segments with 
 
 
 
 k
 
 
 {\displaystyle k}
 
 crossings (or intersections), the Bentley–Ottmann algorithm takes time 
 
 
 
 
 
 O
 
 
 (
 (
 n
 +
 k
 )
 log
 ⁡
 n
 )
 
 
 {\displaystyle {\mathcal {O}}((n+k)\log n)}
 
. In cases where 
 
 
 
 k
 =
 
 
 o
 
 
 
 (
 
 
 
 n
 
 2
 
 
 
 log
 ⁡
 n
 
 
 
 )
 
 
 
 {\displaystyle k={\mathcal {o}}\left({\frac {n^{2}}{\log n}}\right)}
 
, this is an improvement on a naïve algorithm that tests every pair of segments, which takes 
 
 
 
 Θ
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle \Theta (n^{2})}
 
.
The algorithm was initially developed by <a href="/facts/Jon_Bentley_(computer_scientist)/WEK7bgSs">Jon Bentley</a> and Thomas Ottmann (1979); it is described in more detail in the textbooks Preparata & Shamos (1985), O'Rourke (1998), and de Berg et al. (2000). Although <a href="/facts/Asymptotic_analysis/kt87qLpu">asymptotically</a> faster algorithms are now known by Chazelle & Edelsbrunner (1992) and Balaban (1995), the Bentley–Ottmann algorithm remains a practical choice due to its simplicity and low memory requirements.

Bentley–Ottmann algorithm open-in-new

Bentley–Ottmann algorithm