• Voronoi polygon (a) := all points closer to a than other a_i’s.

Verteices 2N-4

edges 3N-6

• Voronoi diagram := polygon(a)
  
  
• Voronoi Dual (Delaunay triangulation) triangulation of all points

• Degree(vertx) = 3 (外心)
  
  

Convex Hull Dual 


• Polygon(a) unbounded a convex Hull

• closest pair ：find closest pair of a_i’s (Dual)
• all nearest neighbor ：find nearest neighbor of a_i (Dual)
• nearest neighbor ：find nearest a_i of a point P (Ppoly(a_i))
• computing convex Hull： (Dual)
• Euclidean Minimum Spanning Tree： (Dual) 
  find a tree connects all a_i’s with minimum distance.
• Can compute Voronoi Diagram in O(NlogN) All can be solved in O(NlogN)

    Compute Voronoi Diagram in O(NlogN) time

        (Divide & Conguer)

        VD=( VD(L) L() ) ( VD(R) R() )
        　

Compute Supporting Lines T=O(N)

1. Compute CH(L)；CH(R)
2. Find interior point P of CH(L)，
3. P interior point of CH(R)？

　

　

4. Merge CH(L)；CH(R)
5. Graham Scan (NlogN for convex Hull)

Property： P：interior point of CH      Angles of vertices of CH