Voronoi Diagram

Given ai, .., aN
Verteices 2N-4

edges 3N-6


 
 

Applications

    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 Pinterior point of CH      Angles of vertices of CH