Bentley–Ottmann algorithm: Difference between revisions

Revision as of 08:44, 4 August 2016

Revision as of 08:02, 23 May 2017

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]],{{sfnp|Shamos|Hoey|1976}} 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''² / log ''n''), this is an improvement on a naïve algorithm that tests every pair of segments, which takes O(''n''²).

The algorithm was initially developed by {{harvs|first1=Jon|last1=Bentley|author1-link=Jon Bentley (computer scientist)|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–OttmanBentley–Ottmann algorithm remains a practical choice due to its simplicity and low memory requirements.

==Overall strategy==

Line 14:

There are two types of events that may happen during the course of this simulation. When ''L'' sweeps across an endpoint of a line segment ''s'', the intersection of ''L'' with ''s'' is added to or removed from the vertically ordered set of intersection points. These events are easy to predict, as the endpoints are known already from the input to the algorithm. The remaining events occur when ''L'' sweeps across a crossing between two line segments ''s'' and ''t''. These events may also be predicted from the fact that, just prior to the event, the points of intersection of ''L'' with ''s'' and ''t'' are adjacent in the vertical ordering of the intersection points.

The Bentley–OttmanBentley–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.

==Data structures==

In order to efficiently maintain the intersection points of the sweep line ''L'' with the input line segments and the sequence of future events, the Bentley–OttmanBentley–Ottmann algorithm maintains two [[data structure]]s:

*A [[binary search tree]], containing the set of input line segments that cross ''L'', ordered by the ''y''-coordinates of the points where these segments cross ''L''. The crossing points themselves are not represented explicitly in the binary search tree. The Bentley–OttmanBentley–Ottmann algorithm will insert a new segment ''s'' into this data structure when the sweep line ''L'' crosses the left endpoint ''p'' of this segment; the correct position of ''s'' in the binary search tree may be determined by a binary search, each step of which tests whether ''p'' is above or below some other segment that is crossed by ''L''. Thus, an insertion may be performed in logarithmic time. The Bentley–Ottmann algorithm will also delete segments from the binary search tree, and use the binary search tree to determine the segments that are immediately above or below other segments; these operations may be performed using only the tree structure itself without reference to the underlying geometry of the segments.

*A [[priority queue]] (the "event queue"), used to maintain a sequence of potential future events in the Bentley–Ottmann algorithm. Each event is associated with a point ''p'' in the plane, either a segment endpoint or a crossing point, and the event happens when line ''L'' sweeps over ''p''. Thus, the events may be prioritized by the ''x''-coordinates of the points associated with each event. In the Bentley–Ottmann algorithm, the potential future events consist of line segment endpoints that have not yet been swept over, and the points of intersection of pairs of lines containing pairs of segments that are immediately above or below each other.

Line 42:

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>

{{harvtxt|Chen|Chan|2003}} described a highly space-efficient version of the Bentley–OttmanBentley–Ottmann algorithm that encodes most of its information in the ordering of the segments in an array representing the input, requiring only O(log²''n'') additional memory cells. However, in order to access the encoded information, the algorithm is slowed by a logarithmic factor.

==Special position and numerical precision issues==