The Bentley-Ottmann algorithm finds all intersection points among a set of line segments in the plane using a sweep line that moves across the segments while maintaining their vertical order in a balanced search structure, reporting an intersection whenever two adjacent segments in that order swap places. It runs in O((n plus k) log n) time, where n is the number of segments and k is the number of intersection points, an improvement over the naive O(n squared) approach of testing every pair of segments. Jon Bentley and Thomas Ottmann described the technique in 1979.
Facts
Time Complexity Credited ToJon Bentley and Thomas Ottmann 2 Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Connections
Credited To
Source Wikipedia: Bentley-Ottmann algorithm
In Field
Source Wikipedia: Bentley-Ottmann algorithm
Invented By
Source Wikipedia: Bentley-Ottmann algorithm
Sources
1. Bentley-Ottmann Algorithm (Wikipedia)
Wikipedia infobox: time complexity linearithmicQuote, Wikipedia infobox: time complexity linearithmic
linearithmic
2. Wikipedia: Bentley-Ottmann algorithm
Lead section, origin sentence
The algorithm was initially developed by Jon Bentley and Thomas Ottmann (1979)
Faster algorithms
If the input line segments and their endpoints form the edges and vertices of a connected graph (possibly with crossings), the O(n log n) part of the time bound for the Bentley-Ottmann algorithm may also be reduced. As Clarkson, Cole & Tarjan (1992) show, in this case there is a randomized algorithm for solving the problem in expected time O(n log* n + k), where log* denotes the iterated logarithm, a function much more slowly growing than the logarithm.
Credited To: Jon Bentley, Lead section
initially developed by Jon Bentley and Thomas Ottmann (1979)
Invented By: Jon Bentley, Lead section
initially developed by Jon Bentley and Thomas Ottmann (1979)
In Field: Algorithms and Complexity Theory, Lead sentence
Bentley-Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e.
In Group: Geometric Intersection, Proximity and Measurement Algorithms, Lead
In computational geometry, the Bentley-Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points (or, simply, intersections) of line segments.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.