Voronoi diagrams
Sweep line algorithm
Fortune's algorithm
Let P be a set of n distinct points (sites) in the plane.
The Voronoi diagram of P is the subdivision of the plane into n cells, one for each site.
A Voronoi cell for p is the set of points q in the plane that are closer to p than to any other site.
i
i
Voronoi diagram constructed as horizontal line sweeps the set of sites from top to bottom
Incremental construction -> maintains portion of diagram which cannot change due to sites below sweep line, keeping track of incremental changes for each site (and Voronoi vertex) it “sweeps”

Beach Line
Voronoi edges are traced by the break points as the sweep line moves down.
– Emergence of a new break point(s) (from formation of a new arc or a fusion of two existing break points) identifies a new edge
Voronoi vertices are identified when two break points meet (fuse).
– Decimation of an old arc identifies new vertex
Fortune's Algorithm For 
Generating Voronoi Diagrams
Lemma: The beach line is an x-monotone curve made up of parabolic arcs. The breakpoints of the beach line lie on Voronoi edges of the final diagram.
Site events
A site event is generated whenever the horizontal sweep line passes over a site.
Circle events
The diagrams
Conclusions
Handling site events
Handling circle events
Total running time
Locate the leaf representing the existing arc
that is above the new site
Delete the potential circle event in the event queue
Break the arc by replacing the leaf node with a
sub tree representing the new arc and break
points
Add a new edge record in the list
Check for potential circle event(s), add them to
queue if they exist
Running Time
O(log n)
O(1)
O(1)
O(1)
Delete from T the leaf node of the
disappearing arc and its associated
circle events in the event queue
Running Time
O(log n)
Add vertex record in list
O(1)
Create new edge record in list
O(1)
Check the new triplets formed by the
former neighboring arcs for potential
circle events
O(1)
Each new site can generate at most two new arcs
beach line can have at most 2n – 1 arcs
at most O(n) site and circle events in the queue
Site/Circle Event Handler O(log n)
O(n log n) total running time
Andrei NECIOV
Emina SZOCS
Thank You!
An arc dissapears whenever an empty circle touches three or more sites and is 
tangent to the sweep line.

Sweep line helps determine that the circle is indeed empty.
Politehnica University of Timisoara
Real Time System Design Masters' Course
Results