Content deleted Content added
No, little o was correct — to replace it by an absolute inequality you need to know more than is stated here about the constant factors in the runtime of the algorithms. |
→Overall strategy: Edited for clarity & accesibility |
||
Line 4:
==Overall strategy==
The main idea of the Bentley–Ottmann algorithm is to use a [[sweep line algorithm|sweep line]] approach, in which a vertical line ''L'' moves from left to right across the plane, intersecting the input line segments in sequence as it moves.<ref>In the description of the algorithm in {{harvtxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2000}}, the sweep line is horizontal and moves vertically; this change entails swapping the use of ''x''- and ''y''-coordinates consistently throughout the algorithm, but is not otherwise of great significance for the description or analysis of the algorithm.</ref>
There are two types of event 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.
| |||