6.2. Computation

6.2. Computation

The construction of the Voronoi diagram has time complexity ˜ ( n log n ). The lower bound ( n log n ) can be achieved by one of the following reductions:

  • a reduction to the convex hull problem is given in [Shamos 78];

  • a reduction to the -closeness problem is given in [Djidjev and Lingas 91] and [Zhu and Mirzaian 91].

Let us briefly discuss the simple convex hull reduction. For a sequence of values x 1 , x 2 , , x n in image from book , we can choose n points p i = ( x i , image from book ) on the parabola y = x 2 in 2D. In the Voronoi diagram of p 1 , p 2 , , p n , the order of the unbounded regions will represent the order of the values x i . We can find the x order of the points p 1 , p 2 , , p n by traversing the DCEL of VD({ p 1 , p 2 , , p n }) adequately. The DCEL has linear size in n . If we can compute the VD( S ) faster than in ( n log n ), we can sort a sequence of values faster than in ( n log n ), which gives a contradiction.

The well-known computation paradigms incremental construction , divide-and-conquer , and sweep are convenient for the construction of the Voronoi diagram. They can also be generalized to other metrics and sites other than points, such as line segments and polygonal chains. The output of the algorithms is stored in a graph of linear size as mentioned earlier. The given approaches run in deterministic time O ( n log n ). The incremental construction and divide-and-conquer approaches for the Voronoi diagram are explained in great detail in [Okabe et al. 92]. A detailed description of the sweepline algorithm can be found in [de Berg et al. 00]. See also [Aurenhammer and Klein 00].

We will concentrate on a simple randomized incremental construction technique, which runs in O ( n log n ) expected time and computes the Delaunay triangulation; see [Guibas et al. 92b]. We make use of an edge-flipping technique introduced in [Lawson 77] and used in [Guibas and Stolfi 85]. Fortunately, the incremental construction technique for the dual of the Voronoi Diagram can easily be generalized to the 3D case, as we will see in Section 6.3.1. But there are some differences. An arbitrary triangulation in 2D can be transformed into a Delaunay triangulation by a sequence of edge flips . It was shown in [Joe 91a] that this is not true in 3D. Fortunately, there are flipping sequences that are successful; see [Rajan 91].

6.2.1. Simple Randomized Incremental Construction for Delaunay Triangulations

Let us assume that the Delaunay triangulation for { p 1 , , p i ˆ1 , p i } was already computed. Let DT i := DT({ p 1 , , p i ˆ1 , p i }). We have to insert the site p i into DT i ˆ 1 in order to obtain DT i .

We will perform edge flip s in DT i ˆ 1 until DT i is finally constructed . A triangle T of DT i ˆ 1 whose circumcircle contains the new site p i is in conflict with p i . By Lemma 6.3, every triangle of DT i ˆ 1 , which is in conflict with p i , will no longer be a Delaunay triangle in DT i . We consider two situations for the location of p i with respect to DT i ˆ 1 .

Case 1: p i lies inside a triangle T = ( p j , p k , p l ). This means that p i is in conflict with T . Surprisingly, the edges p i p j , p i p k , and p i p l will be Delaunay edges in DT i . This can be proven as follows . The edge p i p j will be a Delaunay edge, because there exists a circle contained in Circle( p j , p k , p l ) that contains only p i and p j on its boundary. For the construction of such a circle, we shrink the circumcircle Circle( p j , p k , p l ) holding the contact with p j adequately. Finally, there is a circle inside Circle( p j , p k , p l ) that has only p j and p i on its boundary; see Figure 6.3. The same argument holds for the pairs p i and p k and p i and p l . Therefore, we can insert the Delaunay edges p i p j , p i p k , and p i p l , first.

image from book
Figure 6.3: Adequately shrinking the circumcircle Circle(p j , p k , p l ) and holding the contact with p j shows that there is a circle inside Circle(p j , p k , p l ) that has only p j and p i on its boundary.

Next, we concentrate on the triangles adjacent to the edges of ( p j , p k , p l ) and opposite p i ; for example, let p l p k be an edge of the triangle T = ( q, p k , p l ); see Figure 6.4. If p i is in conflict with T , we flip p l p k by p i q . That is, p l p k is replaced by p i q . We can prove that this edge flip is correct. Since q is opposite p i with respect to p l p k and p i is in conflict with T , q is also in conflict with ( p i , p l , p k ). This is true because every circle passing through p k and p l either contains p i or q (or both); see Figure 6.5. Therefore, p l p k will never be a Delaunay edge again.

image from book
Figure 6.4: An edge flip between p i q and p l p k .
image from book
Figure 6.5: Every circle passing through p k and p l will contain either p i or q. If q , p i , p l , and p k are in non-convex position, then Circle(p i , p l , p k ) cannot contain q because the tangent t pk blocks q .

To see that the edge p i q is a Delaunay edge, we apply the argument of the shrinking circle. We can simply shrink Circle( q, p k , p l ) holding the contact with q only. Circle( q, p k , p l ) has only p i inside because ( q, p k , p l ) was a Delaunay triangle before p i was inserted. Finally, there will be a circle passing through p i and q , which has no other point of S inside or on the boundary.

Altogether, we proceed as follows. We successively extend the star of p i , ˜… ( p i ), the set of new Delaunay edges emanating from p i. As an invariant, the outer points of ˜… ( p i ) build a polygon P ( ˜… ( p i )); see Figure 6.6. In the beginning, P ( ˜… ( p i )) equals ( p j, p k, p l ). For every edge e of P ( ˜… ( p i )), we test the triangles T of DT i ˆ 1 with e ˆˆ T and opposite p i . Opposite means that there is a point q ‰  p i such that q and e build T . If q and p i and the endpoints of e are in convex position, T is called flippable . If T is not flippable, T cannot be in conflict with p i . This is shown as follows. If q and p i and the endpoints p l and p k of e are in non-convex position, the circle Circle( p i , p l , p k ) cannot contain q . Either the chain p i , p l , q or the chain p i , p k , q is concave. Then q lies beyond the prolongation of a secant p i p k or p i p l at Circle( p i , p k , p l ). A tangent of Circle( p i , p l , p k ) at p l or p k separates q from Circle( p i , p l , p k ); see Figure 6.5 for the point q instead of q .

If T is flippable, we test whether T is in conflict with p i . If T is in conflict with p i , we perform an edge flip of e with the edge p i q . ˜… ( p i ) and P ( ˜… ( p i )) are updated adequately. The process stops if the adjacent outer triangles of P ( ˜… ( p i )) are no longer in conflict with p i ; see Figure 6.6.

image from book
Figure 6.6: Successively check the outer triangles of P( ˜… (p i )) for conflicts with p i. The point r is the last point that will evoke an edge flip.

Case 2: p i lies ouside the convex hull of DT i ˆ 1 . In this case, all points q on the boundary of DT i ˆ 1 visible from p i build an edge pq in DT i ; see Figure 6.7. This can be easily seen as follows. The part of the boundary of DT i ˆ 1 visible from p i builds a convex chain. Visible means that the segment p i q is not crossed by segments from DT i ˆ 1 . For every q , there is a tangent t q such that DT i ˆ 1 lies fully on one side and p i lies on the other side. First, we make use of a prolongation of one of the adjacent outer edges of DT i ˆ 1 at q and obtain t q . Then we can expand acircleat q that has tangent t q and meets p i ; see Figure 6.7. With Lemma 6.3, we conclude that qp i is a Delaunay edge. If ˜… ( p i ) is computed for all boundary sites q , we proceed as shown in Case 1, doing some edge flips until the procedure finally stops.

image from book
Figure 6.7: If p i is outside the convex hull of DT i ˆ1 , the starting ˜… (p i ) is given by the visible points on the hull . P ˜… (p i )) is a convex chain opposite p i .

For both cases, we have the following result.

Lemma 6.4. If all segments of P ( ˜… ( p i )) are Delaunay edges, the construction of DT i is completed.

Proof: The circumcircles of all triangles around P ( ˜… ( p i )) do not contain p i, and all segments of P ( ˜… ( p i )) are Delaunay edges. Let T = ( p, q, r ) be a triangle outside P ( ˜… ( p i )) that is in conflict with p i; i.e., the circumcircle Circle( p, q, r ) contains p i . The triangle T was a Delaunay triangle of DT i ˆ 1 ; Circle( p, q, r ) contains only p i . By the same shrinking circle arguments as in Case 1, we know that p i p , p i q , and p i r must be Delaunay edges of DT i . Since T is outside P ( ˜… ( p i )) and all edges of P ( ˜… ( p i )) are Delaunay edges, the edges p i p, p i q, and p i r will cross P ( ˜… ( p i )), which gives a contradiction to the definition of a Delaunay triangulation. T cannot be in conflict with p i .

The edge flips can be carried out efficiently if ˜… ( p i ) is computed efficiently. Altogether, three tasks must be considered .

The following is the edge flip algorithm sketch.

  1. Find the triangle T = T ( p j , p k , p l ) of DT i ˆ1 with p i ˆˆ T and compute the initial ˜… ( p i ) by p i p j, p i p k, and p i p l; then compute P ( ˜… ( p i )).

  2. Otherwise, if p i is not inside DT i ˆ1 , compute the initial ˜… ( p i ) of all segments p i q , where q is visible from p i ; then compute P ( ˜… ( p i )).

  3. Perform all edge flips of P ( ˜… ( p i )) due to conflicts, successively insert new edges into ˜… ( p i ), and update P ( ˜… ( p i )). Stop if no triangle on the boundary of P ( ˜… ( p i )) is in conflict with p i.

Obviously, the third task is bounded by the degree of p i in the new triangulation DT i . The structural work needed in the third task for computing DT i from DT i ˆ 1 is proportional to the degree d of p i in DT i . Therefore, we should try to keep this degree low.

We yield an O ( n 2 ) time algorithm for constructing the Delaunay triangulation of n points. We can determine the triangle of DT i ˆ 1 containing p i within linear time by inspecting all existing candidates. If p i is not inside DT i ˆ1 , we can compute the starting ˜… ( p i )in O ( k + log n ), computing the outer tangents first and moving along k edges for k segments of the initial ˜… ( p i ). The degree of p i is trivially bounded by O ( n ) because any triangulation has no more than O ( n ) edges.

Algorithm 6.1 successively inserts new sites, and Algorithm 6.2 handles the edge flips.

Altogether, we get the following result.

Theorem 6.5. The Delaunay triangulation of a set of n points in the plane can be constructed incrementally in time O ( n 2 ) , using linear space.

We can even do better. The main thing is that we insert the points randomly , thus avoiding worst-case scenarios for the degree of p i in DT i . There can be single vertices in DT i that do have a high degree, but their average degree is bounded by 6. It was shown in [Guibas et al. 92b] that the expected overall number of triangles that appear during a randomized incremental insertion is bounded by O ( n ).

Algorithm 6.1: The incremental construction of the Voronoi diagram.
image from book

Delaunay( S ) ( S represents a set of sites in 2D)

  T  := new DCEL  while   S  =  image from book   do   p  :=  S.  First  S.  DeleteFirst  T.  InsertSite(  p  )  end while  
image from book
 
Algorithm 6.2: Inserting a new site in a Delaunay triangulation.
image from book

T. InsertSite( p ) ( T represents the DCEL of the current Delaunay triangulation; p is a new site)

  t  :=  T.  FindTriangle(  p  )  if   t  = Nil  then   


Geometric Data Structures for Computer Graphics2006
Geometric Data Structures for Computer Graphics2006
ISBN: N/A
EAN: N/A
Year: 2005
Pages: 69

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net