|
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]]. 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'' line segments with ''k'' crossings, the Bentley–Ottmann algorithm takes time O((''n'' + ''k'') log ''n''). In cases where ''k'' = o(''n''<sup>2</sup> / log ''n''), this is an improvement on a naïve algorithm that tests every pair of segments, which takes O(''n''<sup>2</sup>).
The algorithm was initially developed by {{harvs|first1=Jon|last1=Bentley|author1-link=Jon Bentley|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, the Bentley–Ottman algorithm remains a practical choice due to its simplicity and low memory requirements.
The algorithm processes one event per segment endpoint or crossing point, in the sorted order of the ''x''-coordinates of these points, as may be proven by induction. This follows because, once the ''i''th event has been processed, the next event (if it is a crossing point) must be a crossing of two segments that are adjacent in the ordering of the segments represented by ''T'', and because the algorithm maintains all crossings between adjacent segments as potential future events in the event queue; therefore, the correct next event will always be present in the event queue. As a consequence, it correctly finds all crossings of input line segments, the problem it was designed to solve.
The Bentley–Ottmann algorithm processes a sequence of 2''n'' + ''k'' events, where ''n'' denotes the number of input line segments and ''k'' denotes the number of crossings. Each event is processed by a constant number of operations in the binary search tree and the event queue, and (because it contains only segment endpoints and crossings between adjacent segments) the event queue never contains more than 3''n'' events. Thus, all operations take time O(log ''n'') and the total time for the algorithm is O((''n'' + ''k'') log ''n'').
If the crossings found by the algorithm do not need to be stored once they have been found, the space used by the algorithm at any point in time is O(''n''): each of the ''n'' 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 3''n'' elements. This space bound is due to {{harvtxt|Brown|1981}}; the original version of the algorithm was slightly different (it did not remove crossing events from ''Q'' when some other event causes the two crossing segments to become non-adjacent) causing it to use more space.<ref>The nonlinear space complexity of the original version of the algorithm was analyzed by {{harvtxt|Pach|Sharir|1991}}.</ref>
==Faster algorithms==
The O(''n'' log ''n'') part of the time bound for the Bentley–Ottmann algorithm is necessary, as there are matching [[lower bound]]s for the problem of detecting intersecting line segments in [[algebraic decision tree]] models of computation.<ref>{{harvtxt|Preparata|Shamos|1985}}, Theorem 7.6, p. 280.</ref> However, the dependence on ''k'', the number of crossings, can be improved. {{harvtxt|Clarkson|1988}} and {{harvtxt|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 of lines|arrangement]] construction was solved [[deterministic algorithm|deterministically]] in the same O(''n'' log ''n'' + ''k'') time bound by {{harvtxt|Chazelle|Edelsbrunner|1992}}. However, constructing this arrangement as a whole requires space O(''n'' + ''k''), greater than the O(''n'') space bound of the Bentley–Ottmann algorithm; {{harvtxt|Balaban|1995}} described a different algorithm that lists all intersections in time O(''n'' log ''n'' + ''k'') and space O(''n'').
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 {{harvtxt|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-star}} denotes the [[iterated logarithm]], a function much more slowly growing than the logarithm. A closely related randomized algorithm of {{harvtxt|Eppstein|Goodrich|Strash|2009}} solves the same problem in time O(''n'' + ''k'' log<sup>(''i'')</sup>''n'') for any constant ''i'', where log<sup>(''i'')</sup> 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<sup>(''i'')</sup>''n'' factor, for any constant ''i'', while the second algorithm takes linear time whenever ''k'' is smaller than ''n'' by a log<sup>(''i'')</sup>''n'' factor. Both of these algorithms involve applying the Bentley–Ottmann algorithm to small random samples of the input.
==Notes==
|
