Voronoi diagram, Delaunay triangulation and 3D Convex Hull

(Still refinining... this blog entry. More images will be added to aid understanding... hopefully)

Introduction:

In the following discussion, Voronoi diagram and halfplane intersection refer to the 2D case, unless otherwise specified.

I hope I can list some nice properties of as well as some relationships between the following three structures in computational geometry:

• Voronoi diagram
  
  
  
  [You need to understand what is going on on the right image.The left and the middle will be discussed below.]
• Delaunay triangulation
• 3D convex hull 

However, I will skip proofs about these items.

Listed are some assumed knowledge before proceeding:

• Dual of a graph
• 3D geometry intuition
• Idea of halfplane intersection (just an idea is enough)
• Idea of tangent plane to a 3D surface
• Idea of Voronoi diagram
  If you have no idea, play along with this applet to get a feeling!

---

1) Voronoi Diagram and Delaunay Triangulation

For a point set, P, (each point also known as a site) define:

1. V(P) := Voronoi diagram
2. D(P) := Delaunay triangulation := Straight line dual of V(P)
3. V(p) := Region of site p in V(P)

Note: Assume no 4 points in P are cocirular, or there will be degeneracy
(e.g., Property 2. will be broken)

A) Properties:

1. (Intuitive) V(P) is composed of (not all) segments of perpendicular bisectors between sites.
2. V(P) and D(P) are dual to each other.
3. Every face of the D(P) is a triangle.
   (Or we cant name it as triangulation, but this property is not trivial)
4. Following are correspondences between V(P) and D(P) :
   
   
   
   
   
   • Vertex ↔ Triangle
   • Edge ↔ Edge
   • Node ↔ Region
5. Let v be a vertex on V(P), s.t., it is at the junction of V(p₁) , V(p₂), V(p₃).
   Then v is the center of the circumcircle of p1, p2, p3.
   Let C(v) := this circle.
6. The interior of C(v) (in 5.) has no sites, i.e., C(v) is an empty circle.
7. If some circle through p₁, p₂ contains no other sites, then (p₁, p₂) is an edge of D(P). The reverse also holds.
8. Delaunay triangulation maximizes the minimum angle: (最小角最大化)
   Let T be a triangulation of a point set S. Let its angle sequence {α_i} be list of angles of triangles, sorted from smallest to largest. Let {β_i} be the angle sequence for a Delaunay triangulation. Then, we have {β_i} ≥ {α_i} for all T.
   Note 1: Here, "≥" means lexicographically greater than.
   Note 2: D(P) maximizes the 2nd minimum angle, in case the smallest angle ties.
   Note 3: Intuitively, D(P) gives "fatter" triangles - we prefer fatter triangles for its higher numerical stability in other applications.

Application of D(P) and V(P):

1. Nearest neighbors
   The nearest neighbor graph (NNG) is a subset of D(P):
   i.e., if p1 is nearest neighbor to p2, then (p1, p2) is an edge of D(P).
2. Euclidean MST
   The minimum spanning tree of the complete graph for P is a subset of D(P).

B) Implementation / Algorithm for D(P) and V(P):

1. By halfplane intersection - O(N² lg N)
   For a fixed site p, for each other site q, define halfplane h_q := {Points closer to p than q}. Then, V(p) is the intersection of all h_q's, and it can be found in O(N lg N) time. The number of V(p) is O(N), so the overall complexity for computing V(P) is O(N² lg N).
2. Fortune's plane sweep algorithm - Inverted cones intersection - O(N lg N)
   Idea: For each site p, erect a cone whose apex is at p, with sides slope at 45 degree. The Voronoi diagram can be thought as expanding circles from each site. Imagine you cut these (solid) cones with z = c and observe the intersection, you get a moment when the circles are expanding. If you gradually increase c from 0 to ∞, you actually simulate the expansion of these circles. Therefore, when viewing down from z = ∞, you see the Voronoi diagram!
   Note 1: For real implementation, we need to maintain a parabolic front.
   Note 2: That's also why Voronoi diagram can be computed quite quickly using GPU.
3. By 3D convex hull - O(N²) / expected O(N lg N)
   The time complexity is due to 3D convex hull algorithm. See next section.

C) Variations:

1. Furthest point Voronoi diagram
2. Medial axis / Skeleton of a polygon
   = Voronoi diagram, when a site is an edge of a polygon

---

2) 3D Convex Hull   VS   Voronoi Diagram=Delaunay Triangulation

For a point set, P, (each point also known as a site) define:

1. V(P) := Voronoi diagram
2. D(P) := Delaunay triangulation := Straight line dual of V(P)
3. V(p) := Region of site p in V(P)
4. H(P) := 3D convex hull of { f(p) | p ∈ P }
   Paraboloid transformation: f(x, y) := x² + y²

Note: Assume no 4 points in P are cocirular, or there will be degeneracy

A) Properties:

1. Projecting the "lower" part of H(P) onto the x-y plane, we get D(P)
2. Let T_p = the tangent plane at the converted point f(p) to the paraboloid f.
   For site p1, p2, when the intersection of T_p1, T_p2 (a straight line) is projected onto the x-y plane, we get the perpendicular bisector of p1 and p2.
3. If we put tangnet planes of all sites (T_p 's) to the space, and view them from z = ∞, according to Property 2., we will see V(P)!

B) Extension:

1. Extension to higher dimension of Property 2.

---

3) *Extension - Arrangements of lines:

Together with convex hull and Voronoi diagram (= Delaunay triangulation), arrangement of lines are the third important structures used in computaional geomtry, and there are many beautiful properties linking them together. (We already go through some between the former two.)

Furthermore, most of these properties and relationships perserve in higher dimension.

Some topics about arrangement of lines listed below:

• Zone's theorem
• Point / line duality
  There are different possible mappings, but the most convenient one is:
  L : y = 2ax - b ⇔ p : (a, b)
  This mapping is intimately related to the paraboloid transformation, and therefore fullfills many beautiful properties.
• Relationship between halfplane intersection and convex hull

After reading Ch. 6 of Computaional Geometry in C (or some other books or notes), I may write another entry for arrangement of lines.

---

4) External links:

1. Voronoi/Delaunay Applet
2. CS 497: Computational Geometry
   A schedule of a CG course, listing various topics in CG
3. Is there anything new to say about Voronoi diagrams?
   About Voronoi digram in higher dimension
4. Furthest Point Voronoi Diagram
   Discuss the construction algorithm 
5. Point/Line duality
   Applet
6. http://acm-kn.xanga.com/716525481/duality-in-cg/
   When I started to think I really have to know about this for ACM...