Notes on Voronoi and Delaunay Diagrams

Document Sample
Notes on Voronoi and Delaunay Diagrams Powered By Docstoc
					AMS 345/CSE 355                                                                                 Joe Mitchell

                   Notes on Voronoi and Delaunay Diagrams
   Let S = {p1 , . . . , pn } be a set of n points (sites) in the plane.

Deﬁnition of Voronoi diagram. For any subset Q ⊆ S of sites we deﬁne the Voronoi region,
V (Q), for Q to be the set of all points p ∈ 2 such that Q is the set of closest sites to p.
    There are 2n diﬀerent subsets of S, but only a very few of them have a nonempty Voronoi
region, V (Q). In fact, if S has no four cocircular points, then V (Q) is empty for any Q having
|Q| ≥ 4. For each singleton set, Q = {pi }, V (Q) = V ({pi }) is nonempty and is often called the
Voronoi cell associated with site pi . We usually abuse notation slightly and let V (pi ) = V ({pi }).
    By our deﬁnition, V (pi ) is always an open set (it does not include its boundary); this is in
contrast with the notation in O’Rourke, which deﬁnes V (pi ) to be a closed set that includes its
boundary. If Q consists of two points, Q = {pi , pj }, and V (Q) is nonempty, then V (Q) = V ({pi , pj })
is called a Voronoi edge; it will be a subset of the bisector, b(pi , pj ), between pi and pj . Voronoi
edges are open line segments (they do not include their ednpoints). If Q consists of 3 or more
points, then V (Q) will be a single point (or will be empty); we call such points Voronoi vertices.
The Voronoi diagram for S, denoted V(S), is deﬁned to be the partition of 2 into the regions
V (Q), for all Q ⊆ S. The Voronoi diagram is a polygonal subdivision, consisting of vertices, edges,
and (convex) polygonal faces (cells).

Deﬁnition of Delaunay diagram. We deﬁne the Delaunay diagram, D(S), to be the “straight
line dual” of the Voronoi diagram, V(S): Speciﬁcally, we place a Delaunay node (vertex) at each
site pi and we join two sites pi and pj with a straight line segment if and only if the Voronoi cells
V (pi ) and V (pj ) share a common boundary segment (i.e., if and only if the Voronoi edge V ({p i , pj })
exists (is nonempty)). While this deﬁnition gives a speciﬁc recipe for drawing the diagram, which
is deﬁned as a particular drawing of a planar dual graph of the Voronoi diagram, the deﬁnition
alone does not suﬃce to be able to claim that the diagram is “nice” in the sense that no two edges
cross. Since it is a planar dual of a planar graph (the vertices and edges of the Voronoi diagram),
the graph itself must be planar; however, it requires a proof (ﬁrst given by Delaunay) that the
particular drawing we give (with nodes at the sites pi and edges drawn with straight segments) is
a plane graph, having no crossing edges.

Properties of Voronoi/Delaunay Diagrams.

   1. Voronoi cells are the interiors of convex polygons or of “unbounded convex polygons”, whose
      boundary edges are Voronoi edges and whose vertices are Voronoi vertices.

   2. Each Voronoi cell V (pi ) contains the point pi and corresponds to the Delaunay node pi . Each
      Voronoi edge V ({pi , pj }) corresponds to its dual Delaunay edge, (pi , pj ). (NOTE: The line
      segment V ({pi , pj }) need not cross the line segment pi pj . Draw an example!) Each Voronoi
      vertex v = V ({pi1 , pi2 , . . . , pim }) (m ≥ 3) corresponds to its dual Delaunay face; the point v is
      the center of a circle, C, that passes through the sites pi1 , . . . , pim and no other site lies inside
      or on the circle C. (NOTE: The point v need not lie inside the corresponding Delaunay face.
      Draw an example!)
3. The Delaunay diagram is a plane graph (has no crossing edges). (This is Delaunay’s theorem.)
   If there are no four cocircular points, then it is a triangulation of the convex hull of S – the
   Delaunay triangulation. If there are subsets of four or more sites that are cocircular, the faces
   of D(S) may not all be triangles; some may be convex polygons. No site can lie interior to a
   face of D(S).

4. The boundary of the face at inﬁnity of D(S) is the boundary of the convex hull of the
   sites. Those pairs of sites that appear consecutively on the boundary of the convex hull have
   corresponding Voronoi edges that are unbounded (they are rays).

5. pi pj deﬁnes a Delaunay edge if and only if there is a “site-free” circle passing through p i and
   pj , meaning that no sites other than pi and pj lie inside or on the circle.

6. V ({pi , pj }) deﬁnes a (nonempty) Voronoi edge if and only if there is a “site-free” circle passing
   through pi and pj , meaning that no sites other than pi and pj lie inside or on the circle.

7. For any partitioning of the sites S into “red” and “blue” sites (say, R and B), the shortest
   edge (line segment) linking a red site to a blue site must be a Delaunay edge. This fact has

    (a) D(S) is a connected graph.
    (b) N N G ⊆ D(S) (Lemma 5.5.1), where NNG is the nearest neighbor graph. Thus, NNG
        can be computed in time O(n log n).
    (c) M ST ⊆ D(S) (Theorem 5.5.5). A consequence of this is that the MST can be com-
        puted in time O(n log n) for n points in the plane (since Kruskal’s algorithm can be
        implemented in time O(E log E) for an E-edge graph, if one uses the appropriate data
        structures). The MST can be used to obtain a “2-approximation” to a Traveling Sales-
        person tour, as explained in Section 5.5.5. In fact, using a slightly smarter method
        (Christoﬁdes heuristic), a 1.5-approximation can be computed. Using much more so-
        phisticated methods, a (1 + )-approximation can be computed eﬃciently, for any ﬁxed
          > 0.

8. For n ≥ 3, V(S) has at most 2n − 5 Voronoi vertices and at most 3n − 6 Voronoi edges. (Thus,
   for n ≥ 3, D(S) has at most 2n − 5 faces and at most 3n − 6 edges.)
   Thus, the “size” of the Voronoi diagram (in terms of the number of bytes needed to store its
   edges, vertices and faces in, say, a winged-edge data structures) of n sites is O(n). Likewise,
   the size of a Delaunay diagram is linear (O(n)).

9. Assume that no four points of S are cocircular. Then D(S) is a triangulation of the convex
   hull, CH(S), and this triangulation is “optimal” (or “nicest”) in the following precise sense:
   D(S) maximizes the minimum angle of the triangles. More speciﬁcally, if we take the 3t angles
   deﬁned by the t triangles of D(S), and organize them in a sequence (the “angle sequence”),
   α = (α1 , α2 , . . . , α3t ), sorted from smallest to largest, then the Delaunay triangulation lexico-
   graphically maximizes (over all possible triangulations) the vector α. (It maximizes α 1 , the
   smallest angle; subject to that being minimum, it maximizes α2 , etc.) See Section 5.5.2 and
   Theorem 5.5.2.
 10. Given the Voronoi diagram V(S), one can preprocess it in time O(n) in order to support
     “nearest neighbor queries” (ﬁnd the closest site to a query point q ∈ 2 ) that can be answered
     in time O(log n) using “point location” data structures. See Section 7.11.

 11. The largest empty circle having its center within CH(S) must be centered either at a Voronoi
     vertex or at a point on the boundary of CH(S) where a Voronoi edge crosses the boundary
     of CH(S).

 12. If we “lift” the points S onto the paraboloid of revolution, z = x2 + y 2 in 3D, we get a set
     S of points in 3D. (These points are in convex position – each point of S is a vertex of the
     convex hull CH(S ).) The Delaunay diagram D(S) is exactly what one would “see” if we
     look “up” at the convex hull CH(S ); i.e., the edges of CH(S ) that bound facets that are
     the “lower” hull are exactly corresponding to the Delaunay edges. See Theorem 5.7.2. The
     upper hull correspond to the “furthest-point Delaunay”, which is the dual to the “furthest-
     point Voronoi” diagram (a decomposition of the plane into regions according to which site is
     furthest away, rather than closest).

 13. D(S) and V(S) can be computed in time O(n log n), using O(n) space. Algorithms that
     achieve this worst-case time bound can be based on either divide-and-conquer or plane sweep
     (using a clever method of Fortune). If the diagrams are built incrementally, the worst-case
     time bound is O(n2 ); however, if we add sites in random order, the expected running time is
     only O(n log n).

 14. There is a lower bound of Ω(n log n) on the time needed to construct the Voronoi or Delaunay
     diagram of a set of points, if the input is simply the point set. This follows from the fact that
     there is an Ω(n log n) lower bound for computing convex hulls, since the Delaunay diagram
     (or Voronoi) can be used to compute the convex hull in linear time. (i.e., given either one of
     D(S) or V(S), one can easily traverse the diagrams to extract the convex hull in linear (O(n))

 15. If either one of D(S) or V(S) is given, then the other can be computed in time O(n) from it.
     (See problem 2 of Section 5.7.5.)

Algorithms to Build D(S) or V(S) Here is a summary of standard methods to construct the
Voronoi or Delaunay diagram:

  1. Divide and conquer: Split the point set in half (e.g., according to the median x-coordinate),
     recursively build the diagram for each half, and then merge. The tricky part is doing the
     merge eﬃciently; it can be done in time O(n), as I brieﬂy explained in class. Overall, then,
     we get a running time of T (n) ≤ 2T (n/2) + O(n), which solves to T (n) = O(n log n). The
     algorithm uses O(n) space (storing the diagrams, which are planar graphs).

  2. Plane sweep: Steve Fortune devised a clever plane sweep algorithm in 1985 to compute the
     diagrams in O(n log n) time. An overview is in Section 5.4.4.

  3. Incremental construction: By adding points one by one and updating the diagrams, it is
     possible to achieve worst-case time O(n2 ), since the worst-case time for insertion is O(n). In
     fact, the time it takes to insert a new point pi into the existing Voronoi diagram is proportional
      to the number of sides in the cell of pi in the revised diagram; the number of sides is linear
      in the number of sites, but often much smaller in practice.
      In fact, if points are added in random order, it is possible to build the diagrams in expected
      time O(n log n), since, on average, the insertion cost is low (O(log n), which comes from a
      Harmonic series computation).

  4. Flipping algorithms: One can start with any triangulation of S and “ﬂip” diagonals that are
     not “locally Delaunay” until every edge is locally Delaunay. It can be shown that this takes
     time O(n2 ) in the worst case. See Problem 5, Section 5.4.5, and see the notes below.

  5. Because of the connection to convex hulls in 3D, any algorithm that works for convex hulls in
     3D can be used to compute a Delaunay diagram in 2D (and thus also the Voronoi diagram).
     For instance, QuickHull can be used to compute Voronoi and Delaunay diagrams (even in
     higher dimensions; see for the recently released
     QHull 3.0).

Edge-Flipping Algorithm (Lawson) Consider an arbitrary triangulation, T , of S (more pre-
cisely, of the convex hull of S). There are many ways that we can get some triangulation, but often
one is already known to us. (Note, though, that if no triangulation is known, it does take at least
time Ω(n log n) to compute a triangulation of a set of points given in arbitrary order.)
    Each edge of the convex hull, CH(S), is an edge in T and is also an edge in D(S). Thus, our
interest concerns only those interior (non-hull) edges of T . We say that an interior edge e = ab,
bounding the triangles abc and abd, is locally Delaunay if point c does not lie inside the circle
C(a, b, d) through points a, b, and d (which is equivalent to saying that d does not lie inside the
circle through a, b, and c). Basically, e = ab is locally Delaunay if and only if ab is a Delaunay edge
in the Delaunay triangulation of just the four points a, b, c, d. If e = ab is not locally Delaunay, then
the four points a, b, c, d must be in convex position (they deﬁne a convex quadrilateral). Further,
if we replace e = ab with e = cd (we “ﬂip” the diagonal of the quadrilateral acbd), then the new
edge e is now locally Delaunay (because one can prove that a lies outside the circle through b, c
and d). This operation of swapping e for e is called an edge ﬂip.
    The edge ﬂipping algorithm starts with T and repeatedly modiﬁes the triangulation by a series
of edge ﬂips: Just pick any edge that is not locally Delaunay and ﬂip it. After doing so, check the
local neighborhood of triangles to see if the “local Delaunayhood” of any other edge has changed,
and update its status. Continue until all edges are locally Delaunay. There is a theorem that says
that a triangulation is Delaunay if and only if each edge is locally Delaunay (i.e., the local property
holding for all edges implies the global property of Delaunayhood).
    We claim that at most O(n2 ) ﬂips are needed in order to get from any one triangulation T
to the Delaunay. This can be shown using the interpretation of Delaunay triangulation as convex
hulls in 3D, as I explained in class.