Overview
Sweep Line algorithms reduce geometric problems by maintaining active objects intersecting a moving line.
CoreSource checked
Sweep Line Algorithm
Processes geometric events in sorted order as a line moves across the plane.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Advanced
- Family
- Sweep Line
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 6
- Code example
- Not ready
- Visualization
- Ready
- Aliases
- Plane Sweep
Core Concepts
geometric calculationevent sweepgeometric predicatesweep linespatial relationshipcoordinate calculation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n log n)
Average
O((n + k) log n)
Worst
O((n + k) log n)
Space
O(n)
When to Use
- Use Sweep Line Algorithm when you need to sort geometric events.
- Use it for segment intersection with inputs like geometric objects.
- Use it when the problem depends on spatial relationships between points, lines, or shapes.
- Use it when the Sweep Line tradeoff is acceptable for the problem size.
When Not to Use
- Avoid it when floating-point precision or degenerate cases are not handled.
- Avoid it when the required output is not detected intersections or relationships.
What It Does
- Sorts geometric events
- Maintains active objects near the sweep line
Use Cases
- Segment intersection
- Closest pair variants
- Rectangle overlap detection
Inputs
- Geometric objects
- Event ordering rule
Outputs
- Detected intersections or relationships
Pseudocode
- 1.Create sorted event points
- 2.Move the sweep line through events
- 3.Update the active structure
- 4.Check only nearby active objects
- 5.Record detected geometric relationships
Canonical Example
- Input
- points = [(0,0), (2,0), (1,1), (1,0)]
- Output
- spatial result such as a boundary, intersection, or containment answer
- Explanation
- Sweep Line Algorithm: The algorithm uses geometric tests to reason about the input shapes.
Implementation Notes
- Keep the input contract explicit: Geometric objects; Event ordering rule.
- Use this step as the implementation spine: Create sorted event points.
- Then preserve the next state change: Move the sweep line through events.
- Write tests for points on boundaries, equal coordinates, and very small distances.
Common Pitfalls
- Sweep-line solutions depend on careful event ordering and tie handling.
- Forgetting collinear, duplicate, overlapping, or boundary cases.
- Returning detected intersections or relationships without handling empty, invalid, or boundary inputs.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow a vertical line moving across events and updating active segments.
Step 1 of 5: Create sorted event points
moving-sweep-lineNotes
Sweep Line Algorithm operates in O((n + k) log n) time and O(n) space within the Sweep Line family. Often compared with Line Segment Intersection and Delaunay Triangulation.
Sources (2)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookTextbook support for Sweep Line Algorithm's computational geometry problem family, predicates, structures, or geometric construction.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Sweep Line Algorithm in the computational geometry benchmark area.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsFortune's Algorithm
Geometry · Specialized
It is a specialized sweep-line geometry algorithm.
Compare with thisUsed byIncremental Line Arrangement Construction
Geometry · Extended
Incremental Line Arrangement Construction uses Sweep Line Algorithm as a subroutine, representation, or supporting idea while adding lines one at a time and updating affected cells.
Compare with thisRelationships
View full relationship pageGeneralizesBentley-Ottmann Algorithm
Bentley-Ottmann is one sweep-line algorithm.
Often paired withLine Segment Intersection
Sweep-line methods commonly maintain geometric intersection events.
Related Algorithms
Tags
GeometrySweep LineComputational Geometry