Sweep line algorithm
In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all "crossings" in a set of line segments, i.e. it finds the "intersection points" (or, simply, "intersections") 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 formula_1 line segments with formula_2 crossings (or intersections), the Bentley–Ottmann algorithm takes time formula_3. In cases where formula_4, this is an improvement on a naïve algorithm that tests every pair of segments, which takes formula_5.
The algorithm was initially developed by Jon Bentley and Thomas Ottmann (1979); it is described in more detail in the textbooks , , and . Although asymptotically faster algorithms are now known by and , the Bentley–Ottmann algorithm remains a practical choice due to its simplicity and low memory requirements.
Overall strategy.
The main idea of the Bentley–Ottmann algorithm is to use a sweep line approach, in which a vertical line "L" moves from left to right (or, e.g., from top to bottom) across the plane, intersecting the input line segments in sequence as it moves. 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". Specifically, a discrete event can either be associated with an endpoint (left or right) of a line-segment or intersection point of two line-segments. Thus, the continuous motion of "L" can be broken down into a finite sequence of steps, and simulated by an algorithm that runs in a finite amount of time.
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 (or intersection of) 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–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–Ottmann algorithm maintains two data structures:
The algorithm does not need to maintain explicitly a representation of the sweep line "L" or its position in the plane. Rather, the position of "L" is represented indirectly: it is the vertical line through the point associated with the most recently processed event.
The binary search tree may be any balanced binary search tree data structure, such as a red–black tree; all that is required is that insertions, deletions, and searches take logarithmic time. Similarly, the priority queue may be a binary heap or any other logarithmic-time priority queue; more sophisticated priority queues such as a Fibonacci heap are not necessary. Note that the space complexity of the priority queue depends on the data structure used to implement it.
Detailed algorithm.
The Bentley–Ottmann algorithm performs the following steps.
Analysis.
The algorithm processes one event per segment endpoint or crossing point, in the sorted order of the formula_6-coordinates of these points, as may be proven by induction. This follows because, once the formula_7th 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 formula_8, 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 formula_9 events, where formula_1 denotes the number of input line segments and formula_2 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 formula_12 events. All operations take time formula_13. Hence the total time for the algorithm is formula_3.
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 formula_15: each of the formula_1 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 formula_12 elements. This space bound is due to ; the original version of the algorithm was slightly different (it did not remove crossing events from formula_18 when some other event causes the two crossing segments to become non-adjacent) causing it to use more space.
 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 formula_19 additional memory cells. However, in order to access the encoded information, the algorithm is slowed by a logarithmic factor.
Special position.
The algorithm description above assumes that line segments are not vertical, that line segment endpoints do not lie on other line segments, that crossings are formed by only two line segments, and that no two event points have the same "x"-coordinate. 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. suggested perturbing the input slightly to avoid these kinds of numerical coincidences, but did not describe in detail how to perform these perturbations. 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.
Numerical precision issues.
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. 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 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" 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. However, the dependence on "k", the number of crossings, can be improved. and 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 . However, constructing this arrangement as a whole requires space O("n" + "k"), greater than the O("n") space bound of the Bentley–Ottmann algorithm; 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 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 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. Both of these algorithms involve applying the Bentley–Ottmann algorithm to small random samples of the input.
Notes.
 ;templatestyles src="Reflist/styles.css" / ;