Overview
Fortune's Algorithm sweeps across sites, maintaining parabolic arcs that define where Voronoi edges are forming.
SpecializedSource checked
Fortune's Algorithm
Constructs a Voronoi diagram with a sweep line and beach line.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Advanced
- Family
- Sweep Line Geometry
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
site eventcircle eventbeach lineVoronoi edge
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)
When to Use
- Use when a full Voronoi diagram is needed efficiently for many points.
- Use when voronoi diagram generation is a central requirement.
When Not to Use
- Avoid when a simpler nearest-neighbor grid or approximate partition is sufficient.
- Avoid when floating-point precision or degenerate geometry cannot be handled robustly.
What It Does
- Processes site and circle events
- Maintains the beach line
- Emits Voronoi edges and vertices
Use Cases
- Voronoi diagram generation
- Spatial partitioning
- Nearest-site analysis
Inputs
- Set of 2D sites
Outputs
- Voronoi edges and vertices
Key Formulas (1)
Voronoi boundary
distance(p, sitea) = distance(p, siteb)
distance(p, site_a) = distance(p, site_b)Defines points on the edge between two Voronoi regions.
Pseudocode
- 1.Add site events to a priority queue
- 2.Move the sweep line through events
- 3.Update the beach line for site events
- 4.Handle circle events when arcs disappear
- 5.Finish dangling Voronoi edges
Canonical Example
- Input
- sites = three non-collinear points
- Output
- diagram = three Voronoi regions meeting at one vertex
- Explanation
- The sweep creates edges where points are equally near neighboring sites.
Implementation Notes
- Keep event handles so circle events can be marked invalid when arcs disappear early.
- Use robust predicates or tolerances when near-degenerate inputs are expected.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Invalid circle events must be removed or ignored after the beach line changes.
- Collinear, overlapping, and duplicate points need explicit tie-breaking rules.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow a sweep line moving across sites while parabolic beach arcs trace Voronoi edges.
Step 1 of 5: Add site events to a priority queue
geometry-diagramNotes
The beach line data structure and circle event invalidation are the hardest parts.
Sources (2)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookComputational geometry textbook support for Fortune's Algorithm's geometric model, data structures, and robustness concerns.
Open sourceFortune Sweepline Voronoi
PaperOriginal reference for constructing Voronoi diagrams with a sweep-line algorithm.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageVariant ofSweep Line Algorithm
It is a specialized sweep-line geometry algorithm.
SpecializesVoronoi Diagram
Fortune's Algorithm constructs a Voronoi diagram using a sweep line.
Related Algorithms
Tags
GeometrySweep LineComputational GeometrySpatial Index