An incremental algorithm for high order maximum voronoi diagram construction

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 di- Agram 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 algorithm takes O ( ⌈rmax-rmin / dmin⌉ m k²N logN ) time com- plexity, where N, rmax and r min are respectively the number of disks, the maximum and minimum radii of disks, and dmin is the minimum distance between two disk centers. Our algorithm is amiable to distributed implementation.