Lecture 16: Voronoi Diagrams and Fortune's Algorithm

Reading: Chapter 7 in the 4M's.

Because we need to define "distance", we need to now talk about 
euclidean geometry...

Euclidean Geometry: We now will make a subtle but important shift. Up
to know, virtually everything that we have done has not needed the
notion of angles, lengths, or distances (except for our work on
circles). All geometric tests were made on the basis of orientation
tests, a purely affine construct. But there are important geometric
algorithms which depend on nonaffine quantities such as distances and
angles. Let us begin by defining the Euclidean length of a vector 
v = (vx, vy) in the plane to be 

|v| = sqrt(x2 + y2)

The distance between two points p and q, denoted dist(p; q), is
defined to be |p - q|.  (recall that in affine geometry, we weren't
allowed to do the "-" operation on two points.  Euclidean geometry
allows this).


Voronoi Diagrams: Voronoi diagrams (like convex hulls) are among the
most important structures in computational geometry. A Voronoi diagram
records information about what is close to what. Let P =
{p1,p2, ... , pn} be a set of points
in the plane (or in any dimensional space), which we call
sites. Define V(pi), the Voronoi cell for pi, to
be the set of points q in the plane that are closer to pi
than to any other site. That is, the Voronoi cell for pi is
defined to be: V(pi ) = {q | dist(pi,q) <
dist(pj, q), for j != i}:

Another way to define V(pi) is in terms of the intersection
of halfplanes. Given two sites pi and pj, the
set of points that are strictly closer to pi than to
pj is just the open halfplane whose bounding line is the
perpendicular bisector between pi and pj. Denote
this halfplane h(pi, pj). It is easy to see that
a point q lies in V(pi) if and only if q lies within the
intersection of h(pi, pj) for all j != i. In
other words, 

V(pi) = Intersection (for all j) h(pi, pj):

Since the intersection of halfplanes is a (possibly unbounded) convex
polygon, it is easy to see that V(pi) is a (possibly
unbounded) convex polygon. Finally, define the Voronoi diagram of P ,
denoted Vor(P ) to be what is left of the plane after we remove all
the (open) Voronoi cells.  It is not hard to prove (see the text) that
the Voronoi diagram consists of a collection of line segments which
may be unbounded, either at one end or both.


Figure 56: Voronoi diagram
Voronoi diagrams have a number of important applications. These include:

Nearest neighbor queries: One of the most important data structures
problems in com putational geometry is solving nearest neighbor
queries. Given a point set P , and given a query point q, determine
the closest point in P to q. This can be answered by first computing a
Voronoi diagram and then locating the cell of the diagram that
contains q.  (We have already discussed point location algorithms.)

Computational morphology: Some of the most important operations in
morphology (used very much in computer vision) is that of ``growing''
and ``shrinking'' (or ``thinning'') objects. If we grow a collection
of points, by imagining a grass fire starting simultaneously from each
point, then the places where the grass fires meet will be along the
Voronoi diagram. The medial axis of a shape (used in computer vision)
is just a Voronoi diagram of its boundary.


Facility location: We want to open a new Blockbuster video. It should
be placed as far as possible from any existing video stores? Where
should it be placed? It turns out that the vertices of the Voronoi
diagram are the points that locally at maximum distances from any
other point in the set.

High clearance path planning: A robot wants to move around a set of
obstacles. To mini mize the possibility of collisions, it should stay
as far away from the obstacles as possible.  To do this, it should
walk along the edges of the Voronoi diagram.  


Properties of the Voronoi diagram:

Here are some observations about the structure of Voronoi diagrams in
the plane.

Voronoi edges: Each point on an edge of the Voronoi diagram is
equidistant from its two nearest neighbors pi and
pj. Thus, there is a circle centered at such a point such
that pi and pj lie on this circle, and no other
site is interior to the circle.

Voronoi vertices: It follows that vertex at which three Voronoi cells
V(pi), V(pj), and V(pk) intersect is
equidistant from all sites. Thus it is the center of the circle
passing through these sites, and this circle contains no other sites
in its interior.

Degree: If we assume that no four points are cocircular, then the
vertices of the Voronoi diagram all have degree three.

Convex hull: A cell of the Voronoi diagram is unbounded if and only if
the corresponding site lies on the convex hull. (Observe that a point
is on the convex hull if and only if it is the closest point from some
point at infinity.)

Size: If n denotes the number of sites, then the Voronoi diagram is a
planar graph (if we imagine all the unbounded edges as going to a
common vertex infinity) with exactly n faces. It follows from Euler's
formula that the number of Voronoi vertices is at most 2n - 5 and the
number of edges is at most 3n - 6. (See the text for details.)

Computing Voronoi Diagrams: There are a number of algorithms for
computing Voronoi diagrams. Of course, there is a naive
O(n2 log n) time algorithm, which operates by computing
V(pi) by intersecting the n - 1 bisector halfplanes
h(pi, pj), for j != i. However, there are much
more efficient ways, which run in O(n log n) time. Since the convex
hull can be extracted from the Voronoi diagram in O(n) time, it
follows that this is asymptotically optimal in the worst case.

Historically, O(n2) algorithms for computing Voronoi
diagrams were known for many years (based on incremental
constructions). When computational geometry came along, a more
complex, but asymptotically superior O(n log n) algorithm was
discovered. This algorithm was based on divide and conquer. But it was
rather complex, and somewhat difficult to understand.  Later, Steven
Fortune invented a plane sweep algorithm for the problem, which
provided a simpler O(n log n) solution to the problem. It is his
algorithm that we will discuss. Somewhat later still, it was
discovered that the incremental algorithm is actually quite efficient,
if it is run as a randomized incremental algorithm. We will discuss
this algorithm later when we talk about the dual structure, called a
Delaunay triangulation.


This course is modeled on the Computational Geometry Course taught by
Dave Mount, at the University of Maryland.  These notes are
modifications of his Lecture Notes, which are copyrighted as follows:


Copyright, David M. Mount, 2000, Dept. of Computer Science,
University of Maryland, College Park, MD, 20742. These lecture notes
were prepared by David Mount for the course CMSC 754, Computational
Geometry, at the University of Maryland, College Park. Permission to
use, copy, modify, and distribute these notes for educational purposes
and without fee is hereby granted, provided that this copyright notice
appear in all copies.