MIT OpenCourseWarehttp://ocw.mit.edu 6.854J / 18.415J Advanced Algorithms Fall 2008��For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.18.415/6.854 Advanced Algorithms December 3, 2008 Lecture 23 Lecturer: Michel X. Goemans 1 Voronoi Diagrams 1.1 Introduction Suppose we are given a set P of points in the Euclidean plane, and we are interested in the problem of, given a point x, find the closest point of P to x. One approach to this problem is to divide the plane into regions associated with each pi ∈ P for which x is closest to pi. Finding these regions in two dimensions is the problem of constructing the Voronoi Diagram. One application of this structure is to compute the mimumum spanning tree of a complete graph of n vertices in the Euclidean plane in time O(n log n). 1.2 Definitions We will focus on the two-dimensional case. We are given a set P = {p1, p2, . . . , pn} ⊆ R2 and we want to partition the plane into regions which c orrespond to points which are closest to a specific point. Figure 1: Voronoi Diagram (solid lines) for four points p1, p2, p3, p4. 23-1� �Definition 1 (Voronoi Cell) Given a set of points in R2 , P = {p1, p2, . . . , pn} ⊆ R2, a Voronoi Cell V (pi) is defined by: V (pi) = {x : d(pi, x) < d(pj , x) ∀j =� i}. Another way to define a Voronoi Cell is by defining h(pi, pj) to be the halfplane containing pi defined by the bisector of pi and pj . A cell is then defined as: V (pi) = h(pi, pj ). j=i This impies that every cell is convex and is a (convex) polygonal region with at most n − 1 sides. Definition 2 (Voronoi Diagram) A Voronoi Diagram is a collection of Voronoi cells that covers R2 . 1.3 Motivation Why is a Voronoi Diagram useful? If the points represent firestations, the Voronoi cells represent the partition of the plane into regiosn which are closer to each firestation. More generally, given a point in a plane, it is useful to know the point from a set of points that is closest to it. Of course, this also requires a data structure to be able to answer the point location problem of, given x, finding the Voronoi cell that contains it. We will only learn how to construct the Voronoi diagram, not how to build a query datastructure for it. . Having such a diagram is useful for many problems. For example, a Voronoi diagram allows computation of the Euclidian minimum spanning tree on a set of points in O(n log n) time, see the problem set. 1.4 Properties The Voronoi cells are all disjoint and their closures cover the entire plane. The Voronoi diagram will consist of edges (possibly semi-infinite, extending to infinity) and vertices where 3 or more of these edges meet; these vertices will be equidistant to 3 or more points of P . One can characterize the vertices and the edges in the following way: Lemma 1 1. A point q ∈ R2 is a vertex of a Voronoi Diagram ⇐⇒ there exists an empty circle (i.e. its interior is empty) centered at q having at least 3 points of P on its boundary. 2. Part of the bisector between pi and pj is an edge of the Voronoi diagram ⇐⇒ there exists an empty circle centered at a point q having precisely pi and pj (and no other point) on its boundary. 23-2� We look now at how ’complex’ a Voronoi diagram can be. We know that each cell is delimited by at most n − 1 sides (edges), but in the lemma below, we show that collectively all cells do not have too many edges and vertices. Lemma 2 For a Voronoi diagram with n points, the following relations hold: • The number of vertices of a Voronoi diagram is nv ≤ 2n − 5. • The number of edges in any Voronoi diagram is ne ≤ 3n − 6. Figure 2: To prove Lemmma 2 we add a point q∞ to the Voronoi Diagram (solid lines), and connect all of the infinite edges to this point (shown in dotted lines). Proof: We can view the Voronoi diagram as a planar graph, G, with some edges extending out to infinity. We add a point at infinity q∞ representing ‘infinity’ and connect edges that extend to infinity to this point as shown in Figure 2. Note that the resulting graph G� is still planar. The number of vertices in G� is nv + 1; the number of edges is ne, and the number of faces is n. By Euler’s formula, we have nv + 1 − ne + n = 2. Since we know that vertices will have at least 3 edges incident to them, we obtain, by summing the degrees over all vertices, that: d(v) = 2ne ≥ 3(nv + 1). vertices v 23-3� Combining this with Euler’s formula, we get: 2(nv + 1) + 2n ≥ 4 + 3(nv + 1) or 2n − 5 ≥ nv. Using this in Euler’s formula, we now get ne = nv − 1 + n ≤ 3n − 6. 2 Computation of Voronoi Diagrams 2.1 Introduction There are two primary algorithms we want to introduce. Both of these will be shown to compute the Voronoi diagram in time O(n log n). First, we can reduce the com-putation of the Voronoi diagram to that of a convex hull in R3, which is computable in time O(n log n); this is our first algorithm. Secondly, we will review the sweep line algorithm of Fortune [1]. 2.2 Convex Hull Figure 3: Projection of a point onto a paraboloid in R3 . To use the convex hull to compute the Voronoi diagram, this projection is done for all points in the set of points for which we want to compute the Voronoi diagram. Suppose we have a set P ⊆ R2 and we want to compute the corresponding Voronoi diagram. Let us consider the set P � = {(xi, yi, xi 2 +yi 2) : (xi, yi) ∈ P }. This projection onto a parabola is shown in Figure 3. 23-4Consider the set of planes tangent to each point in P �. The intersection of the upper half spaces of these planes gives a polyhedral set Q whose projection back to R2 gives the Voronoi diagram in the following sense: the projection of the facets (resp. edges, vertices) of Q gives the Vornoi cells (resp. edges, vertices) of the Voronoi diagram. This computation can be done in O(n log n) time since this calculation is the geometric dual of the convex hull computation. If, instead, we were to compute the convex hull of P � (rather than the halfs-paces tangent to the paraboloid at P �) and project it back to R2, we would obtain a straight-line drawing on P (dual to the Voronoi diagram) known as the Delaunay Triangulation, see problem set. 2.3 Sweep Line Algorithm The idea of a sweep line algorithm is