Computing the Delaunay Triangulation in Computational Geometry

Lecture Notes for Introduction to Computational Geometry (Com S 418/518) Yan-Bin Jia, Iowa State University Computing the Delaunay Triangulation Outline: I. Edge legalization II. Correctness III. Use of a trapezoidal map IV. Analyses of storage and run time Textbook: Computational Geometry: Algorithms and Applications (3rd ed.) by M. de Berg et al., Springer-Verlag, 2008.

I. The Construction Problem Input: a set ? of ? points. Algorithm 1 1) Compute the Voronoi Diagram Vor(?). ?3 ?4 ?1 2) Obtain DG(?). ?2 ?5 ?6 3) Triangulate faces with > 3 vertices. ? ?7 ?8

Randomized Incremental Construction Algorithm 2 Point 1) Introduce a set ={?0,? 1,? 2} of three auxiliary points such that ?0? 1? 2 contains all points from ? in the interior. Start with ?0? 1? 2. ? 2 ?0 ? 1

Point Addition 2) Add points in random order, maintaining a Delaunay triangulation of the current set. Point In step ?, find the triangle ?????? that contains the newly added ??. ?? ?? ?? ?? ?? ?? ?? ?? ?? Case 2: ?? on an edge Case 1: ?? in the interior of ??????

Legal and Illegal Edges Add edges from ?? to the vertices of the containing triangle(s). Point The new edges incident on ?? are legal (to be shown in Lemma 1). ?? ?? ?? ?? ?? ?? ?? ?? ?? Replace illegal edges by legal edges through edge flips.

Edge Legalization LegalizeEdge(??,????,?) Point 1. if ???? is illegal 2. then let ?????? and ?????? be adjacent along ???? 3. replace ???? with ???? 4. LegalizeEdge(??,????,?) 5. LegalizeEdge(??,????,?) ?? ?? All recursive calls involve edges opposing ??. All replacing edges during the edge flips are incident on ??. ?? ?? An edge (which was legal before) can only become illegal if one of its two incident triangles has changed. Only the edges of the new triangles need to be checked.

More Observations LegalizeEdge(??,????,?) Point 1. if ???? is illegal 2. then let ?????? and ?????? be adjacent along ???? 3. replace ???? with ???? 4. LegalizeEdge(??,????,?) 5. LegalizeEdge(??,????,?) ?? ?? Only the edges of the new triangles need to be checked. ?? ?? ???? and ???? are newly inserted and legal (to be shown). So check ???? and ???? opposing ??, and recursively from there.

Iterations 1. Compute a random permutation ?1,?2 ,?? 2. for ? 1 to ? 3. do 4. find ?????? ?? in the current triangulation ? 5. if ?? lies in its interior 6. then // case 1 7. add edges ????, ????, ???? 8. LegalizeEdge(??,????,?) 9. LegalizeEdge(??,????,?) 10. LegalizeEdge(??,????,? 11. else // case 2 12. add edges ????, ???? 13. LegalizeEdge(??,????,?) 14. LegalizeEdge(??,????,?) 15. LegalizeEdge(??,????,?) 16. LegalizeEdge(??,????,?) Point ?? ?? ?? ?? ?? ?? ?? ?? ??

II. Correctness Need to prove that no illegal edges remain after all calls to LegalizeEdge. Correctness is implied by the following: Point Every new edge due to insertion of a point ?? is incident to ??. Ensured by the recursive calls. Every new edge is legal. To be shown in Lemma 1 next. Any edge that may become illegal is tested. Because an edge can only become illegal if one of its incident triangles changes. Algorithm terminates because every flips increases the angle vector of the triangulation.

Legality of Every New Edge Lemma 1 Every new edge created during the insertion of ?? is an edge of ??({?0,? 1,? 2,?1, ,??}). Point Proof Examine two types of edges. The 1st type of edges (cases 1 & 2) are added right after insertion of ??. ?? ?? ?? ?? ?? ?? ?? ?? ?? Case 1 Case 2

Immediately Added Edges Case 1 Point ??????is a triangle in ??( ?1, ,?? 1). ?? ? The circumcircle ? of ??,??,?? contains no point ??, ? < ?, in its interior. ?? Shrink ? (centered at ?) to a circle ? centered at ? on ??? and passing through ?? and ??. ? is empty. ????an edge of the DG after addition of ??. ? ?? ? ?? ? Similarly, ????and ???? are edges too. Case 2 Similar to Case 1.

Edges Added Due to Flipping The 2nd type of edges are added due to flipping by LegalizeEdge. Point Suppose ????of ??????is replaced by ????. ?? ??????was a Delaunay triangle and its circumcircle ? (centered at ?) contains ?? in its interior only. ?? ? Shrink ? to a circle ? with only ?? and ?? on its boundary. ? ? ?? ? is closer to ?? than to ??. ?? ? Move on ???from ? toward ?? until reaching a location ? that is equidistant to both ?? and ?? ? (centered at ? and through ?? and ??) is empty. ????is a Delaunay edge after the addition.

III. Locating the Containing Triangle Build a point location structure ? as a directed acyclic graph. Point Trapezoidal map with only triangles no trapezoids. Leaves: triangles of the current triangulation ?. ? Internal nodes: triangles that existed before but have been destroyed. ? ?? ?? ?? Initialized as a DAG with one node ( ?0? 1? 2). ?? ? ? ?? ? ? ? ? ?

Example 1 2 3 3 2 insert ?? into 1 split 1 1 ?? ?? 4 3 2 1 2 ?? 3 4

Insertion Locate ?? in ??({? 2,? 1,?0,?1, ,?? 1}) Start at the root ( ?0? 1? 2) of ?. ?? 1 Check its three children to see which one contains ??. ?? 2 ?? created from addition of ?1 (which is in the interior of ?0? 1? 2) 3 Descends to this child. Repeat the above two steps to reach a leaf. Time linear in #nodes on the search path = #triangles stored in ? that contains ??

Example (contd) ?? 1 2 3 ?? ?? 6 5 4 ?? ?? 3 5 6 flip ???? ?? ?? ?? 4 3 2 1 2 ?? ?? 3 4

Example (finish) 1 2 3 ?? ?? 6 5 4 ?? ?? 3 5 6 flip ???? 1 2 3 ?? ?? 4 6 6 7 ?? 8 5 ?? 8 7

Selecting ?2,?1,?0 ? = max ??=(??,??) 1 ? ? { ??,|??|} Point ? 1= (0,3M) ?0lies outside circles defined by any three points in ?. (M,M) ? 1lies outside circles defined by any three points in ? {?0}. ?0= (3M,0) ( M, M) ? 2lies outside circles defined by any three points in ? {?0, ? 1}. ? 2= ( 3M, 3M)

IV. Analysis ??= {?1,?2, ,??} ???= ??( ? 2,? 1,?0,?1, ,??) Point Lemma 2 Expected number of triangles created (and deleted) by the algorithm is 9? + 1. ProofOne triangle ?0? 1? 2 at the start. Iteration ? inserts ??: ?? ?? Split 1 or 2 triangles, creating 3 or 4 new ones, and the same number of edges. ?? ?? ?? ?? ?? Every edge flipped in the subsequent LegalizeEdge results in creation of an edge adjacent to ??and 2 new triangles bordering this edge. ?? ??

Proof of Lemma 2 (contd) Suppose ? edges in ??? are incident to ?? at the end of the iteration. Iteration ? starts with (right after inserting ??) one of two cases below: ?? ?? ?? ?? ?? ?? ?? ?? ?? 3 new edges 4 new edges 3 new triangles 4 new triangles

Triangles Generated in One Iteration Iteration ? ends with ? 3 more new edges, each from a flip ? 4 more new edges due to flips 2(? 4) more new triangles 1 new edge 2 new triangles 2(? 3) more new triangles #new triangles due to iteration ? max{2 ? 3 + 3,2 ? 4 + 4} = 2? 3

Backward Analysis Let deg ??,??? = ? be the degree of ?? in ???. Apply backward analysis to determine its expected value. Fix the set ??= ?1,?2, ,?? but view ??as a random element from the set. ??? has the same number ( 3 ? + 3 6) of edges as the Voronoi diagram Vor(({? 2,? 1,?0,?1, ,??}). Three of the edges are ? 1? 2, ? 1?0, ? 2?0. Total degree of vertices from ?? is 2(3 ? + 3 9) = 6?. Expected degree of such a vertex is 6.

Proof of Lemma 2 (finish) Expected # triangles created in step ? Point i.e., 2? 3 shown two slides earlier ?(2deg ??,??? 3) = 2?(deg ??,???) 3 Expected degree 6 from previous slide = 2 6 3 = 9 ? insertion steps 9? triangles created Include ?0? 1? 2 9? + 1 triangles.

Storage and Run Time Theorem 3??(?) can be computed in ? ?log? expected time using ?(?) expected storage. Point Sketch of Proof (Storage) Every node of the search structure corresponds to a triangle. By Lemma 2, expected number of triangles is ?(?). (Time) Time cost is attributed to two types of operations: all point location steps remaining portion # created triangles ?(?)

Expected Time to Locate a Point Time to locate ?? # nodes visited in the search structure Point # triangles that were present at some earlier stage and containing ?? but have been destroyed One triangle may be charged multiple times, each time for locating a different point. ?: set of all triangles created by the algorithm. ? : number of points from ? that lie within the triangle Total time for all point location steps is ? ? + ?? = ?(?log?) (for proof see Lemma 9.13)