An Incremental Algorithm for High Order Maximum Voronoi Diagram Construction.
Khuong Vu, Rong Zheng · 2011
We propose an incremental approach to compute the order-k maximum Voronoi diagram of disks in the plane. In our approach, we start with an order-k Voronoi diagram of disk centers and iteratively expand disks and update the changes of the diagram until all disks reach their targeted size. When disks expand continuously, the structure of the (⌈diagram changes ⌉ discretely. The rmax−rmin algorithm takes O k dmin