Forest-like abstract Voronoi diagrams in linear time

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. [1] 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) along the boundary of D is given, then V(S) inside D can be constructed in linear time.