Fortune's Algorithm for Voronoi Diagrams

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

Given a finite set of points (called sites) in a plane, a Voronoi diagram divides the plane into regions around each site that are closer to that site than to any of the others. This Demonstration shows Fortune's algorithm for drawing Voronoi diagrams [1].

[more]

Two auxiliary curves are involved in the procedure:

1. The sweep line (green) can move up or down; only sites above it are active.

2. The beach line (red) is a sequence of parabolic arcs. Each parabola has an active site for its locus and the sweep line as directrix.

The intersections of two parabolic arcs (the breakpoints on the beach line) have equal distance to two sites (the foci of the two parabolas) and to the sweep line. Thus, as the sweep line moves down, these intersection points determine the rest of the diagram.

[less]

Contributed by: Erik Mahieu (July 2016)
Open content licensed under CC BY-NC-SA


Snapshots


Details

Reference

[1] S. Fortune, "A Sweepline Algorithm for Voronoi Diagrams," Algorithmica, 2, 1987 pp. 153–174. www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send