Forest-like abstract Voronoi diagrams in linear time
Abstract Voronoi diagrams are a general framework covering many types of concrete diagrams for different types of sites or distance measures. Generalizing a famous result by Aggarwal et al. we prove the following. Suppose it is known that inside a closed domain D the Voronoi diagram V(S) is a tree, and for each subset S'⊂S, a forest with one face per site. If the order of Voronoi regions of V(S) a