Sweep line algorithm
The sweep line algorithm is a foundational technique in computational geometry that involves sweeping an imaginary line, typically vertical or horizontal, across a plane containing a set of geometric objects, such as line segments or points, while processing discrete events—like the endpoints of segments or potential intersections—as the line progresses monotonically from one side of the plane to the other.[1] This paradigm discretizes continuous geometric problems into a sequence of manageable updates, enabling efficient computation by maintaining dynamic data structures that track the current state of the sweep.[2]
At its core, the algorithm relies on two primary data structures: an event queue, implemented as a priority queue or balanced binary search tree, which stores and orders all event points by their position along the sweep direction (e.g., x-coordinate for a left-to-right sweep), supporting insertions and deletions in O(log n) time where n is the number of objects; and a status structure, also a balanced binary search tree, which maintains the ordered list of objects currently intersected by the sweep line, sorted by their intersection points (e.g., y-coordinates), to facilitate neighbor queries and updates in O(log n) time.[1] These structures ensure that only relevant local interactions, such as adjacency checks between neighboring objects, are performed at each event, avoiding exhaustive pairwise comparisons.[2]
The paradigm gained prominence through the Bentley–Ottmann algorithm, introduced in 1979, which applies it to report all intersections among a set of n line segments in the plane with an output-sensitive time complexity of O((n + k) log n), where k is the number of intersections reported.[3] This marked a significant advancement over naive O(n²) methods, leveraging the sweep to predict and verify intersections only between adjacent segments in the status.[1]
Beyond line segment intersections, the sweep line algorithm underpins numerous applications in computational geometry, including the construction of Voronoi diagrams and Delaunay triangulations via Fortune's algorithm, Boolean operations on polygons such as union and intersection, map overlay in geographic information systems, and motion planning among polygonal obstacles by computing visibility graphs.[1] Its efficiency and adaptability have made it indispensable for handling large-scale geometric data in fields like computer graphics, robotics, and GIS.[2]
Overview
Definition and Basic Concept
The sweep line algorithm, also known as the plane sweep algorithm, is a fundamental paradigm in computational geometry for solving problems involving geometric objects in the plane. It simulates a conceptual vertical line that moves continuously from left to right across the plane, processing the objects it encounters in a systematic manner. This approach transforms complex geometric computations into a sequence of manageable updates by focusing on the line's position and the objects it intersects at any given time.
At its core, the algorithm divides the problem into two interrelated components: maintaining a status representing the current state of objects intersected by the sweep line, and handling discrete events that trigger changes to this status, such as the start or end of an object or a significant interaction between objects. The sweep line's movement is event-driven, advancing only to the next relevant position where the status requires updating, which ensures efficiency by avoiding unnecessary computations between events. This paradigm relies on an event queue to prioritize these occurrences by their x-coordinates and a status structure to track and query the active objects, enabling the resolution of geometric relationships incrementally.[4]
To illustrate the basic concept intuitively, consider a simplified one-dimensional version where the goal is to sort a set of points by their x-coordinates. Here, the sweep line moves from left to right, with each point serving as an event that is inserted into a status list (initially empty) in the order encountered. As the line progresses, the status maintains the sorted order of processed points, demonstrating how the paradigm processes discrete events to build a global solution without comparing all pairs upfront. This 1D sweep highlights the efficiency of event-driven processing, which scales to higher dimensions in full plane sweep applications.
History
The sweep line algorithm was first introduced by Michael I. Shamos and Dan Hoey in 1976 at the 17th Annual Symposium on Foundations of Computer Science, where they presented it as a technique for detecting intersections among a set of line segments in the plane in O(n log n) time.[5] Their approach used a vertical line sweeping across the plane from left to right, maintaining an ordered list of active segments intersected by the sweep line to efficiently check for intersections.[6] This innovation marked an early milestone in computational geometry, building on prior ideas from divide-and-conquer methods and addressing the need for sub-quadratic time algorithms in geometric problems.[6]
The algorithm gained broader applicability through an extension by Jon Bentley and Thomas Ottmann in 1979, who developed a method to report all pairwise intersections among n line segments in O((n + k) log n) time, where k is the number of intersections reported.[7] Their work refined the sweep line paradigm by incorporating an event queue to handle endpoint and intersection events, along with a balanced binary tree for the status structure, enabling the handling of output-sensitive complexity.[7] Early conceptual influences on the sweep line included scanning techniques from sorting algorithms, such as those in merge sort, and plane sweep methods for computing arrangements of lines and segments, which emphasized ordered processing of geometric primitives.[6]
During the 1980s and 1990s, the sweep line technique evolved significantly through applications in more complex geometric constructions, including Voronoi diagrams and map overlay problems. Steven Fortune adapted the paradigm in 1986 to compute Voronoi diagrams of n points in O(n log n) time using a parabolic wavefront transformation and a beach line status structure.[8] In parallel, the algorithm underpinned solutions to map overlay, where intersecting planar subdivisions are combined, leveraging segment intersection detection to achieve efficient merging of polygonal maps.[9]
The sweep line algorithm received modern recognition and standardization in influential textbooks, such as "Computational Geometry: Algorithms and Applications" by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, first published in 2000 and updated in subsequent editions, which presented it as a foundational paradigm in the field.[9]
Core Components
The Sweep Line
The sweep line is defined as an infinite vertical line that translates monotonically across the plane from left to right.[3] This movement occurs at a constant conceptual speed, starting from x = -\infty and progressing to x = +\infty, systematically partitioning the geometric objects relative to its current position.[3] In this paradigm, segments or other objects are classified as either to the left (already processed), intersecting the line (active), or to the right (pending).
A key invariant of the sweep line algorithm ensures that, at any given position, the status reflects precisely the objects currently intersected by the line, such as line segments ordered by their intersection points along the line.[3] This invariant is maintained to capture the dynamic ordering of active objects without redundant computations elsewhere in the plane. The sweep line's position is parameterized solely by its x-coordinate, which serves as the primary sweep parameter to ensure orderly progression.[3] For vertical objects or positions where multiple events share the same x-coordinate, ties are resolved by considering y-coordinates to maintain a consistent total order.
Conceptually, the sweep line visualizes a continuous traversal of the plane, akin to a broom sweeping debris, where the "debris" consists of geometric features encountered in sequence.[3] However, to achieve computational efficiency, the algorithm discretizes this process by detecting and responding only at event points—discrete locations where the status would otherwise change—thus avoiding the impracticality of monitoring the line's position continuously. This approach transforms a potentially infinite continuous problem into a finite sequence of updates, leveraging the monotonicity of the sweep for optimal time complexity in reporting intersections or constructing diagrams.[3]
Event Queue
The event queue in a sweep line algorithm serves as a priority-based data structure that schedules the discrete events encountered by the sweeping line as it moves across the input space, ensuring they are processed in the correct temporal order. It is typically implemented as a balanced binary search tree, such as an AVL tree or red-black tree, which supports efficient insertion, deletion, and minimum extraction operations in O(log n) time, where n is the number of events.[10] This structure maintains events ordered primarily by their x-coordinate in ascending order, with ties broken by y-coordinate in ascending order to resolve vertical positions along the sweep line.[11][10]
The events stored in the queue fall into two main categories: site events, which correspond to the start (left endpoints) and end (right endpoints) of input segments, and intersection events, which represent predicted crossing points between segments discovered during the sweep.[12] Site events are inserted at the algorithm's initialization phase, where all left and right endpoints of the segments are added to the queue, resulting in an initial set of 2n events for n segments.[11] Intersection events are added dynamically as the sweep progresses; when neighboring segments in the status structure are found to cross to the right of the current sweep position, a new event is inserted into the queue at the computed intersection coordinate.[12] Deletions occur when the next event is extracted for processing using a minimum operation, removing it from the queue, and invalid events (such as predicted intersections that no longer occur due to prior swaps) can be deleted explicitly if supported by the implementation.[10]
When multiple events share the same x-coordinate, the queue's ordering ensures they are processed in y-coordinate order from bottom to top, but implementations often impose additional type-based priorities to maintain correctness—for instance, processing left endpoints before intersection events and right endpoints last at the same position, preventing premature deletions or missed updates in the status structure.[10] This handling accommodates up to O(m log n) time for m coincident events at a single point, contributing to the overall efficiency of the algorithm.[10]
Status Structure
In the sweep line algorithm, the status structure maintains a dynamic set of line segments that currently intersect the sweep line, ordered vertically by their y-coordinates at the sweep line's current x-position.[2] This ordering ensures that the structure reflects the relative positions of the segments along the sweep line at any given moment, capturing the vertical arrangement of intersections.[13]
The status is typically implemented using a balanced binary search tree, such as a red-black tree or AVL tree, which supports efficient dynamic updates and queries in O(log n) time per operation, where n is the number of segments.[2] This choice allows for logarithmic-time insertion and deletion of segments as the sweep line advances, as well as predecessor and successor queries to identify immediate neighbors in the ordering.[14]
Key operations on the status include inserting a new segment when its left endpoint is encountered by the sweep line, deleting a segment when its right endpoint is reached, and finding the segments immediately above or below a given segment to check for potential intersections.[13] These neighbor queries are crucial for detecting intersections by examining only adjacent segments in the current ordering.[2]
The structure upholds an invariant that it always contains exactly the active segments intersecting the sweep line, sorted by y-coordinate, and is updated only at discrete event points to maintain this order without continuous recomputation.[14]
Algorithm Framework
General Procedure
The sweep line algorithm operates on a set of geometric primitives, such as line segments, in the Euclidean plane, assuming no degeneracies like vertical segments, overlapping segments, or three segments concurrent at a single point unless handled explicitly. These assumptions simplify the event ordering and status maintenance, allowing the algorithm to process events in a well-defined sequence without additional resolution mechanisms.
Initialization begins by populating the event queue with all initial events, typically the endpoints of the input primitives (e.g., left endpoints for a vertical sweep from left to right), sorted by their position along the sweep direction, such as x-coordinate. The status structure starts empty, representing no primitives intersecting the sweep line at the outset. This setup ensures the algorithm begins with a clean state, ready to advance the sweep line incrementally.
The main loop proceeds while the event queue is not empty: the next event is dequeued, the status is updated to reflect the current position of the sweep line (e.g., inserting or deleting primitives that intersect it), the event is handled according to its type, and any new events—such as potential future intersections with neighboring primitives—are inserted into the queue if they lie ahead in the sweep direction. This iterative process maintains the invariant that all processed regions to the left (or above, for horizontal sweeps) of the current sweep line position are fully analyzed, with intersections reported as they are detected.
Termination occurs once the event queue is exhausted, at which point all events have been processed, and the algorithm outputs the accumulated results, such as a list of reported intersections. The final status is typically discarded, as the complete solution resides in the output collected during event handling.
The following pseudocode outlines the general framework:
sweep_line(input):
initialize event queue Q with endpoints of input primitives
initialize empty status structure T
while Q is not empty:
event = dequeue next event from Q
update status T for event
handle event (report if applicable)
insert new events into Q if needed (e.g., future intersections)
return output results (e.g., intersections)
sweep_line(input):
initialize event queue Q with endpoints of input primitives
initialize empty status structure T
while Q is not empty:
event = dequeue next event from Q
update status T for event
handle event (report if applicable)
insert new events into Q if needed (e.g., future intersections)
return output results (e.g., intersections)
This structure integrates the event queue and status to achieve efficient processing, with specific event handling varying by application but adhering to the same loop.
Event Processing
In the sweep line algorithm, event processing involves handling discrete events encountered by the advancing sweep line, such as segment endpoints and predicted intersections, to maintain the algorithm's invariants and detect relevant geometric features. Each event triggers specific updates to the status structure and event queue, ensuring that only adjacent segments in the current status are checked for potential intersections to the right of the sweep line. This process is central to the efficiency of the paradigm, as exemplified in the Bentley-Ottmann algorithm for line segment intersections.
For a site event at the left endpoint of a line segment, the segment is inserted into the status structure, ordered by its y-intercept with the current sweep line position. The algorithm then checks for intersections between this new segment and its immediate neighbors above and below in the status; if an intersection point lies to the right of the sweep line, it is added as a predicted event to the queue, while any prior predicted events involving these pairs are removed to avoid duplicates. This insertion and neighbor check ensure that the status reflects all active segments correctly without missing imminent crossings.[15]
At a site event corresponding to the right endpoint of a segment, the segment is removed from the status structure. Following removal, the newly adjacent segments—previously separated by the departing one—are tested for intersections to the right of the sweep line, with any valid intersection added to the event queue after removing obsolete predictions. This step prevents overlooking crossings that become possible only after the segment ends.[15]
An intersection event occurs when the sweep line reaches a predicted crossing point of two segments. The algorithm reports this intersection as output, then swaps the order of the two segments in the status to reflect their updated relative positions post-crossing. Subsequently, each swapped segment is checked against its new non-intersecting neighbor (the one above the upper segment and below the lower one) for further intersections to the right, adding valid predictions to the queue while invalidating prior ones. This swapping and rechecking maintains the adjacency invariant critical for detecting all crossings.[15]
To handle degeneracies, such as multiple events at the same x-coordinate or vertical segments, the algorithm processes events in a strict order when ties occur. When multiple events occur at the same x-coordinate, they are processed in order of increasing y-coordinate to maintain the correct status updates. Degeneracies such as vertical segments, overlapping segments, or multiple segments sharing endpoints require special handling in robust implementations, often involving exact arithmetic, careful event ordering, and additional checks to report all valid intersections without duplicates. These rules, formalized in robust implementations, ensure correctness without assuming general position.[16]
Reporting of results, such as intersection points, occurs primarily at intersection events, though endpoint events may trigger reports if an intersection coincides exactly with a segment end under degeneracy handling. Outputs are collected in a list to avoid duplicates, providing a complete enumeration of detected features for the problem at hand.
Key Applications
Line Segment Intersection
The line segment intersection problem involves finding all intersection points among a set of n line segments in the plane, where the number of such intersections is k, potentially up to O(n^2) in the worst case.[7] The sweep line algorithm addresses this by reporting all k intersections in O((n + k) \log n) time, which is output-sensitive and efficient when k is small relative to n^2.[7] This approach assumes no three segments meet at a single point and segments are in general position to avoid degeneracies, though extensions handle such cases.[2]
In this adaptation, the sweep line moves from left to right across the plane, processing three types of events: left endpoints of segments, right endpoints, and intersection points between segments.[17] The event queue is a priority queue ordered by x-coordinate (and y-coordinate for ties), initially containing all endpoint events, with intersection events added dynamically as they are predicted.[7] The status structure maintains the segments currently intersecting the sweep line, ordered by their y-coordinate intersection points with the line (from bottom to top), using a balanced binary search tree for O(\log n) insertions, deletions, and neighbor queries.[17]
The algorithm proceeds as follows: At a left endpoint event, the segment is inserted into the status structure at its appropriate y-position, and potential intersections are checked only with its immediate upper and lower neighbors in the status, as non-adjacent segments cannot intersect without prior adjacent crossings.[7] Any predicted intersection to the right of the sweep line is added to the event queue. At an intersection event, the intersecting segments are reported, swapped in the status structure to reflect their new y-ordering, and each is then checked for intersections with its new neighbors.[2] At a right endpoint event, the segment is deleted from the status, and the newly adjacent upper and lower segments are checked for future intersections.[17] This ensures all intersections are detected exactly once, as the sweep line guarantees that intersecting pairs become adjacent in the status before crossing.[7]
For non-intersecting segments, the algorithm simply processes endpoints without adding intersection events, resulting in O(n \log n) time as k=0.[17] Multiple intersections are handled naturally: if a segment intersects several others, each crossing generates a separate event where swaps propagate checks to new neighbors, ensuring all are reported without duplication, though careful tie-breaking in the event queue prevents redundant processing at coincident points.[7] This application is realized by the Bentley-Ottmann algorithm, which integrates these sweep line components for complete intersection reporting.[7]
Voronoi Diagram Construction
The Voronoi diagram of a set of n point sites in the plane is a partitioning of the plane into n regions, each region consisting of all points closer to one particular site than to any other site, where distance is measured by the Euclidean metric.[18] Each region, known as a Voronoi cell, is a convex polygon (possibly unbounded) bounded by segments of the perpendicular bisectors between the site and its nearest neighbors.[18]
The sweep line algorithm adapts the general framework to this proximity problem by employing a horizontal sweep line that moves downward across the plane, processing sites in decreasing order of their y-coordinates.[18] The status structure maintains the "beach line," an x-monotone chain of parabolic arcs that represents the lower envelope of parabolas defined by each processed site with the sweep line as directrix; these arcs delineate the current wavefront of growing Voronoi cells.[18] Events are of two types: site events, triggered when the sweep line encounters a new site, and circle events, which occur when the sweep line is tangent to an empty circle passing through three consecutive sites on the beach line, signaling the disappearance of an arc.[18] The beach line is dynamically updated to preserve the order of arcs from left to right, enabling efficient neighbor queries.[18]
Fortune's algorithm, introduced in 1987, implements this sweep line approach to compute the Voronoi diagram in O(n log n) time and O(n) space.[18] At a site event for a new site p, the algorithm locates the arc on the beach line directly above p using binary search on the ordered status, splits that arc into left and right portions, and inserts a new parabolic arc for p between them, while initiating two new Voronoi edges emanating from their intersection point.[18] A circle event arises when three consecutive arcs meet at a point on the sweep line, corresponding to a Voronoi vertex at the center of the empty circle tangent to the three sites; the algorithm then removes the middle arc and connects the adjacent arcs with a new edge segment, while propagating potential new circle events to neighboring triples.[18] Voronoi edges are constructed by tracing the paths of breakpoints (intersections of adjacent arcs) as the sweep line advances, starting from site events and terminating at circle events or infinity.[18]
The output is the full Voronoi diagram, represented as a planar graph where vertices correspond to the centers of the empty circles from circle events, and edges are the bisector segments connecting these vertices, forming the dual to the Delaunay triangulation of the sites.[18]
The trapezoidal decomposition addresses the problem of preprocessing a set of non-intersecting line segments that form a planar subdivision into a collection of trapezoids, enabling subsequent point location queries to determine which face of the subdivision contains a given query point in O(log n) expected time, where n is the number of segments. This decomposition augments the input subdivision by adding vertical line segments, called "walls," extending upward and downward from each endpoint until they meet adjacent segments or boundaries, resulting in faces that are either trapezoids (with exactly two non-parallel sides vertical) or triangles.[19] The structure supports efficient navigation for queries by associating the trapezoids with a search tree that guides point location based on coordinate comparisons.[20]
The sweep line algorithm is adapted for this task by employing a vertical sweep line that moves from left to right across the plane, detecting vertical extensions from segment endpoints to form the walls and identifying horizontal trapezoid boundaries defined by the input segments.[21] Events are triggered primarily at the left and right endpoints of segments (processed in increasing x-order), with additional events at intersection points if the input allows crossings, though for strict planar subdivisions, intersections occur only at shared endpoints.[19] Intersection detection during the sweep can be handled via the status structure to ensure proper wall placement without altering the non-crossing assumption.[22]
The algorithm proceeds by maintaining a status structure that tracks the active edges currently intersected by the sweep line, ordered by their y-intersection coordinates to facilitate neighbor searches for wall extensions.[21] At each endpoint event, the sweep line stops, and vertical rays are conceptually "shot" upward and downward from the endpoint to locate the nearest active edges above and below, defining the new trapezoid boundaries; these rays become the vertical walls, splitting existing trapezoids and creating new faces.[19] The status is updated by inserting or deleting edges as the sweep progresses—adding a segment at its left endpoint and removing it at the right—while simultaneously building nodes in the accompanying search structure to link the emerging trapezoids.[22] For efficiency, the status often uses a balanced binary search tree to support O(log n) insertions, deletions, and neighbor queries.
The output is a binary search tree, known as the trapezoidal map or search tree, where leaf nodes represent the individual trapezoids (each storing its four bounding walls and adjacent neighbors), and internal nodes serve as decision points with search keys: x-nodes keyed on the x-coordinate of a vertical wall for horizontal splitting, or y-nodes keyed on a horizontal segment for vertical splitting.[20] Traversing this tree for a query point involves comparing the point's coordinates against the keys at each internal node, leading directly to the containing trapezoid leaf in O(log n) steps on average. The decomposition itself has O(n) size, with at most 6n vertices and 3n trapezoids for n input segments.[19]
As an example, consider a simple polygon with holes represented as a planar subdivision of non-intersecting segments; the sweep line processes the leftmost vertices first, extending vertical walls from each internal vertex to split the polygon's interior into a series of connected trapezoids, such as dividing a rectangular room with a circular hole into four to six trapezoids by adding walls from hole vertices to the outer boundary.[21] This results in a query structure where a point inside the polygon can be located by descending the tree, first checking x-keys to narrow horizontally, then y-keys to pinpoint the vertical slab containing the point.
Advanced Variants and Extensions
Bentley-Ottmann Algorithm
The Bentley-Ottmann algorithm, introduced in 1979 by Jon Louis Bentley and Thomas Ottmann, is an optimal sweep line method for reporting all pairwise intersections among a set of n line segments in the plane without constructing the full arrangement.[3] It employs a priority queue, implemented as a balanced binary search tree, for the event queue to manage endpoints and predicted intersections sorted by x-coordinate, and a balanced binary search tree for the status structure to maintain active segments ordered by their y-intersection with the sweep line.[2] The algorithm achieves O((n + k) log n) time complexity, where k is the number of reported intersections, by processing only O(n + k) events with O(log n) time per operation for insertions, deletions, and neighbor queries.[3]
Key innovations of the algorithm include its output-sensitive design, which avoids enumerating all possible O(n²) pairs by predicting intersections only between adjacent segments in the status structure, and efficient handling of segment swaps at intersection points to update the vertical order without redundant checks.[2] Intersections are detected by computing the intersection point of the lines supporting neighboring segments and checking if it lies within both segments and to the right of the current sweep line; for two adjacent segments s and t, this ensures only potential future crossings are added to the event queue.[3][23] This neighbor-based prediction ensures that only potential crossings are added to the event queue, enabling efficient reporting without full pairwise testing.[2]
The algorithm's procedure can be outlined in pseudocode as follows:
Algorithm Bentley-Ottmann(S):
// S: set of n line segments
Initialize empty event queue Q as balanced BST sorted by x-coordinate (ties broken by y)
Initialize empty status structure Y as balanced BST sorted by y-order at current sweep line
For each segment s in S:
Insert left endpoint of s into Q
Insert right endpoint of s into Q
While Q is not empty:
e = Extract minimum event from Q // leftmost event
If e is a left endpoint of segment s:
Insert s into Y
Let l and r be left and right neighbors of s in Y (if exist)
If l exists and l intersects s to the right of current x, insert intersection into Q
If r exists and r intersects s to the right of current x, insert intersection into Q
Else if e is a right endpoint of segment s:
Let l and r be left and right neighbors of s in Y (if exist)
Delete s from Y
If l and r exist and l intersects r to the right of current x, insert intersection into Q
Else: // e is an intersection point of segments s and t
Report intersection e
Swap s and t in Y // update y-order
Let l_s, r_s be new neighbors of s; l_t, r_t of t
If l_s exists and l_s intersects s to the right of current x, insert intersection into Q
If r_s exists and r_s intersects s to the right of current x, insert intersection into Q
If l_t exists and l_t intersects t to the right of current x, insert intersection into Q
If r_t exists and r_t intersects t to the right of current x, insert intersection into Q
Algorithm Bentley-Ottmann(S):
// S: set of n line segments
Initialize empty event queue Q as balanced BST sorted by x-coordinate (ties broken by y)
Initialize empty status structure Y as balanced BST sorted by y-order at current sweep line
For each segment s in S:
Insert left endpoint of s into Q
Insert right endpoint of s into Q
While Q is not empty:
e = Extract minimum event from Q // leftmost event
If e is a left endpoint of segment s:
Insert s into Y
Let l and r be left and right neighbors of s in Y (if exist)
If l exists and l intersects s to the right of current x, insert intersection into Q
If r exists and r intersects s to the right of current x, insert intersection into Q
Else if e is a right endpoint of segment s:
Let l and r be left and right neighbors of s in Y (if exist)
Delete s from Y
If l and r exist and l intersects r to the right of current x, insert intersection into Q
Else: // e is an intersection point of segments s and t
Report intersection e
Swap s and t in Y // update y-order
Let l_s, r_s be new neighbors of s; l_t, r_t of t
If l_s exists and l_s intersects s to the right of current x, insert intersection into Q
If r_s exists and r_s intersects s to the right of current x, insert intersection into Q
If l_t exists and l_t intersects t to the right of current x, insert intersection into Q
If r_t exists and r_t intersects t to the right of current x, insert intersection into Q
This pseudocode captures the explicit steps for insertion (at left endpoints, with neighbor checks), deletion (at right endpoints, with neighbor rechecks), and intersection handling (reporting, swapping, and updating predictions via intersection tests between new neighbors).[2][3]
The algorithm assumes general position, including no vertical segments, no intersections at endpoints, no three or more segments meeting at a single point, all endpoints having distinct x-coordinates, and no overlapping segments; violations require degeneracy handling, such as symbolic perturbations or explicit case analysis, which complicates implementation but preserves correctness.[2][23]
As a foundational contribution to computational geometry, the Bentley-Ottmann algorithm has influenced numerous subsequent methods, including extensions for counting intersections and applications in map overlay and Voronoi diagrams, establishing the sweep line paradigm for efficient geometric querying. Modern implementations are available in libraries like CGAL.[3][2][24]
Higher-Dimensional Sweeps
The sweep line paradigm extends to three dimensions by replacing the line with a sweep plane that moves parallel to the yz-plane along the x-direction. In this setup, events are no longer discrete points but curves traced on the sweep plane as it intersects edges or features of the input geometry, such as polyhedra boundaries. The status structure evolves into a two-dimensional data structure that maintains the current cross-section of the objects intersected by the plane, ordered to detect changes like intersections or topological updates.[25]
Key applications of this 3D extension include detecting intersections between convex polyhedra, where the sweep plane processes potential overlap regions by tracking evolving polygonal slices, and constructing tetrahedralizations for mesh generation, which generalize 2D Delaunay triangulations to volume decompositions. In higher dimensions, hyperplane sweeps similarly handle d-dimensional intersections or simplicial complexes. These methods achieve a time complexity of O(n \log n + k), where n is the input size (e.g., number of vertices or facets) and k is the output size (e.g., number of intersections), applicable to both 3D and higher-dimensional cases for problems like polyhedral intersections.[25][26]
Challenges arise from the increased dimensionality, particularly in managing event queues that require priorities based on hyperplane positions, often using balanced binary search trees or priority queues to handle curve-based events efficiently. The status structure's complexity grows, as it must dynamically maintain (d-1)-dimensional arrangements, leading to higher costs for insertions, deletions, and neighbor queries compared to 2D cases.[26][25]
Notable examples include computing arrangements of surfaces, where a sweep plane traverses the space to build the full subdivision induced by intersecting quadrics or algebraic surfaces, reporting vertices, edges, and cells. Plane sweeps also facilitate unions of polyhedra by merging cross-sectional polygons as the plane advances, enabling efficient Boolean operations on 3D solids.[27][25]
Developments around 2000 have integrated randomized incremental construction with hyperplane sweeps, enhancing efficiency for higher-dimensional Delaunay triangulations and tetrahedralizations by randomizing insertion order to achieve expected linear-time updates per element, often yielding practical O(n \log n) performance overall.[26]
Complexity and Analysis
Time and Space Complexity
The sweep line algorithm, in its standard formulation for computational geometry problems such as line segment intersection reporting, exhibits a time complexity of O((n + k) \log n), where n is the number of input objects (e.g., line segments) and k is the number of output events or intersections reported. This bound is achieved by the Bentley-Ottmann algorithm, which processes O(n + k) events, each requiring O(\log n) time for data structure operations.
The space complexity is O(n), primarily due to the event queue and status structure, each maintaining at most O(n) elements using balanced binary search trees that consume O(1) additional space per node.
This time complexity derives from the event types and processing costs: each of the n input segments generates two endpoint (site) events, yielding $2n such events initially, while each reported intersection adds one event to the queue, for a total of O(n + k) events. At each event, insertions or deletions in the status structure (a balanced tree ordering active segments by y-coordinate at the current sweep position) and neighbor checks for potential intersections take O(\log n) time; specifically, endpoint events involve O(1) neighbor checks that may queue up to two future intersection events (with the upper and lower adjacent segments), but these are amortized across all events without exceeding the overall bound. The \log n factor arises uniformly from tree operations in both the priority queue for events (ordered by x-coordinate, with ties broken by y) and the status structure.
Several factors influence the practical complexity: geometric degeneracies, such as multiple segments intersecting at a single point, can increase k significantly, though the algorithm handles coincident events by processing them in y-order without additional asymptotic cost. Vertical segments, parallel to the sweep line, require special handling—such as treating them as spanning the entire active range and processing their endpoints with y-ordering—but incur only O(1) extra time per event. Overall, this complexity is superior to the naive O(n^2) approach of checking all pairwise intersections, particularly when intersections are sparse (k \ll n^2).
Optimizations
One key optimization in sweep line algorithms, particularly the Bentley-Ottmann variant for line segment intersections, involves fractional cascading to enhance the efficiency of neighbor searches in the status structure. This technique shares search paths between the event queue and the status data structure, enabling amortized O(1) time for finding adjacent elements, which reduces the overall time complexity from O((n + k) log n) to O(n log n + k), where n is the number of segments and k is the number of intersections reported.[28]
Degeneracies, such as multiple segments sharing endpoints or overlapping collinear segments, can cause combinatorial explosions or undefined behaviors in sweep line processing; these are resolved using symbolic perturbation methods like the simulation of simplicity, which symbolically perturbs input coordinates with small ε terms to ensure generic positions without altering the combinatorial structure. This approach avoids explicit case handling by assuming infinitesimal perturbations that break ties consistently in orientation predicates, maintaining the algorithm's correctness while using exact arithmetic for evaluations. Alternatively, exact arithmetic libraries implement robust predicates to compute orientations and incidences precisely, preventing floating-point errors from introducing spurious degeneracies.[29]
Parallelization improves scalability on multi-core systems by dividing the input space into strips and processing independent sweep lines concurrently, as in the parallel plane sweep algorithm, which uses preprocessing to split segments and post-processing to merge results without frequent synchronization. This distributes event processing across p cores, achieving speedups of up to 6.4x on 8-core systems for synthetic data and 3.3x for geographic inputs, while preserving the serial algorithm's invariants through careful strip boundaries. Priority queues can further enable concurrent event handling in multi-threaded environments.[30]
In practice, sweep line implementations often output results in a doubly connected edge list (DCEL) representation to efficiently store planar subdivisions, such as trapezoidal maps or arrangements, where faces, edges, and vertices are linked bidirectionally for subsequent queries like point location. To handle floating-point precision issues, which can lead to incorrect intersection detections or ordering errors, developers employ adaptive exact predicates that expand to higher-precision arithmetic only when necessary, ensuring robustness without full exact computation overhead.
Empirical studies on sweep line variants, such as those for Delaunay triangulation, show they perform well for input sizes n < 10^5, often outperforming alternatives in uniform distributions due to predictable event processing, but exhibit higher constant factors compared to randomized incremental methods, which require fewer geometric tests like diagonal swaps (e.g., 74% fewer in some benchmarks). For larger n up to 10^6, optimized sweep-circle variants achieve runtimes around 2 seconds on standard hardware, though they lag behind randomized approaches in clustered data due to queue management overhead.[31]