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–itk) + 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 algorithm has time-complexityO(k ² n logn) and space-complexityO(kn). It is the only nontrivial algorithm known for constructing order-kc Voronoi diagrams of sites withadditive weights. It is fairly simple and of practical interest also in the special case of unweighted sites.Work on this paper has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862.