Bentley–Ottmann algorithm: Difference between revisions

Revision as of 17:18, 13 July 2012

Revision as of 12:11, 21 December 2012

Line 1:

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''). ThisIn iscases awhere significant''k'' = o(''n''²), this is an improvement on a naivenaïve algorithm that tests every pair of segments, which would taketakes O(''n''²).

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.

Line 33:

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>

Line 46:

A similar approach to degeneracies was used in the [[Library of Efficient Data types and Algorithms|LEDA]] implementation of the Bentley–Ottmann algorithm.<ref name="LEDA">{{harvtxt|Bartuschka|Mehlhorn|Náher|1997}}.</ref>

For the correctness of the algorithm, it is necessary to determine without approximation the above-below relations between a line segment endpoint and other line segments, and to correctly prioritize different event points. 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]]. However, it may be possible to speed up the calculations and comparisons of these coordinates by using [[floating point]] calculations and testing whether the values calculated in this way are sufficiently far from zero that they may be used without any possibility of error.<ref name="LEDA"/> The exact arithmetic calculations required by a naivenaïve implementation of the Bentley–Ottmann algorithm may require five times as many bits of precision as the input coordinates, but {{harvtxt|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.

==Faster algorithms==

The O(''n''&nbsp; log&nbsp; ''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''&nbsp; log&nbsp; ''n''&nbsp; +&nbsp; ''k''), and this problem of [[arrangement of lines|arrangement]] construction was solved [[deterministic algorithm|deterministically]] in the same O(''n''&nbsp; log&nbsp; ''n''&nbsp; +&nbsp; ''k'') time bound by {{harvtxt|Chazelle|Edelsbrunner|1992}}. However, constructing this arrangement as a whole requires space O(''n''&nbsp; +&nbsp; ''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''&nbsp; log&nbsp; ''n''&nbsp; +&nbsp; ''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''&nbsp; log&nbsp; ''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''&nbsp; log*&nbsp; ''n''&nbsp; +&nbsp; ''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''&nbsp; +&nbsp; ''k''&nbsp; 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. Both of these algorithms involve applying the Bentley–Ottmann algorithm to small random samples of the input.

==Notes==