The algorithm was initially developed by Jon Bentley 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).
[2] The algorithm is described most easily in its general position, meaning: In such a case, L will always intersect the input line segments in a set of points whose vertical ordering changes only at a finite set of discrete events.
The Bentley–Ottmann algorithm itself maintains data structures representing the current vertical ordering of the intersection points of the sweep line with the input line segments, and a collection of potential future events formed by adjacent pairs of intersection points.
It processes each event in turn, updating its data structures to represent the new set of intersection points.
Rather, the position of L is represented indirectly: it is the vertical line through the point associated with the most recently processed event.
Note that the space complexity of the priority queue depends on the data structure used to implement it.
The algorithm processes one event per segment endpoint or crossing point, in the sorted order of the
As a consequence, it correctly finds all crossings of input line segments, the problem it was designed to solve.
input line segments corresponds to at most one node of the binary search tree T, and as stated above the event queue contains at most
This space bound is due to Brown (1981); the original version of the algorithm was slightly different (it did not remove crossing events from
[3] Chen & Chan (2003) described a highly space-efficient version of the Bentley–Ottmann algorithm that encodes most of its information in the ordering of the segments in an array representing the input, requiring only
However, in order to access the encoded information, the algorithm is slowed by a logarithmic factor.
In other words, it doesn't take into account corner cases, i.e. it assumes general position of the endpoints of the input segments.
However, these general position assumptions are not reasonable for most applications of line segment intersection.
de Berg et al. (2000) describe in more detail the following measures for handling special-position inputs: A similar approach to degeneracies was used in the LEDA implementation of the Bentley–Ottmann algorithm.
For this reason it is standard to use integer coordinates for the endpoints of the input line segments, and to represent the rational number coordinates of the intersection points of two segments exactly, using arbitrary-precision arithmetic.
[4] The exact arithmetic calculations required by a naïve implementation of the Bentley–Ottmann algorithm may require five times as many bits of precision as the input coordinates, but Boissonat & Preparata (2000) describe modifications to the algorithm that reduce the needed amount of precision to twice the number of bits as the input coordinates.
The O(n log n) part of the time bound for the Bentley–Ottmann algorithm is necessary, as there are matching lower bounds for the problem of detecting intersecting line segments in algebraic decision tree models of computation.
Clarkson (1988) and Mulmuley (1988) both provided randomized algorithms for constructing the planar graph whose vertices are endpoints and crossings of line segments, and whose edges are the portions of the segments connecting these vertices, in expected time O(n log n + k), and this problem of arrangement construction was solved deterministically in the same O(n log n + k) time bound by Chazelle & Edelsbrunner (1992).
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.
A closely related randomized algorithm of Eppstein, Goodrich & Strash (2009) solves the same problem in time O(n + k log(i)n) for any constant i, where log(i) denotes the function obtained by iterating the logarithm function i times.
The first of these algorithms takes linear time whenever k is larger than n by a log(i)n factor, for any constant i, while the second algorithm takes linear time whenever k is smaller than n by a log(i)n factor.