ORDER-K VORONOI DIAGRAMS OF SITES WITH ADDITIVE WEIGHTS IN THE PLANE

It is shown that the order-k Voronoi diagram of n sites with additive weights in the plane has at most (4k-2)(n-k) vertices, (6k-3)(n-k) edges, and (2k-1)(n-k) + 1 regions. These bounds are approximately the same as the ones known for unweighted order-k Voronoi diagrams. Furthermore, tight upper bounds on the number of edges and vertices are given for the case that every weighted site has a nonempty region in the order-1 diagram. The proof is based on a new algorithm for the construction of these diagrams which generalizes a plane-sweep algorithm for order-1 diagrams developed by Steven Fortune. The new algorithms has time-complexity O(k2n log n) and space-complexity O(kn). It is the only nontrivial algorithm known for constructing order-k Voronoi diagrams of sites with additive weights. It is fairly simple and of practical interest also in the special case of unweighted sites.