The Inverse Voronoi Problem in Graphs II: Trees.

We consider the inverse Voronoi diagram problem in trees: given a tree T with positive edge-lengths and a collection U of subsets of vertices of V(T), decide whether U is a Voronoi diagram in T with respect to the shortest-path metric. We show that the problem can be solved in O (N + n log 2 n) time, where n is the number of vertices in T and N = n + ∑ U ∈ U | U | is the size of the description of the input. We also provide a lower bound of Ω (n log n) time for trees with n vertices. [ABSTRACT FROM AUTHOR]