Bentley–Ottmann algorithm: Difference between revisions

Revision as of 15:56, 27 May 2009

Revision as of 17:00, 27 May 2009

Line 47:

==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|Chazelle|EdelsbrunnerBalaban|19921995}} leftdescribed asa andifferent openalgorithm problemthat the question of whether it is possible to reportlists all segment intersections deterministically in time O(''n''&nbsp;log&nbsp;''n''&nbsp;+&nbsp;''k'') time and space O(''n'') space.

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* 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.

Line 55:

==References==

*{{citation|last=Balaban|first=I. J.|contribution=An optimal algorithm for finding segments intersections|title=Proc. 11th ACM Symp. Computational Geometry|year=1995|pages=211–219|doi=10.1145/220279.220302}}.

*{{citation|last1=Bartuschka|first1=U.|last2=Mehlhorn|first2=K.|author2-link=Kurt Mehlhorn|last3=Näher|first3=S.|contribution=A robust and efficient implementation of a sweep line algorithm for the straight line segment intersection problem|title=[http://www.dsi.unive.it/~wae97/proceedings/ Proc. Worksh. Algorithm Engineering]|year=1997|url=http://www.dsi.unive.it/~wae97/proceedings/ONLY_PAPERS/pap13.ps.gz|editor1-first=G. F.|editor1-last=Italiano|editor2-first=S.|editor2-last=Orlando}}.

*{{citation|last1=Bentley|first1=J. L.|author1-link=Jon Bentley|last2=Ottmann|first2=T. A.|title=Algorithms for reporting and counting geometric intersections|journal=IEEE Transactions on Computers|volume=C-28|issue=9|pages=643–647|year=1979|doi=10.1109/TC.1979.1675432}}.