The Inverse Voronoi Problem in Graphs II: Trees

Identifier:  imarina:9002818

Handle: https://hdl.handle.net/20.500.11797/imarina9002818

Authors:  Bonnet, Edouard; Cabello, Sergio; Mohar, Bojan; Perez-Roses, Hebert

Abstract:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature. 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+ nlog 2n) 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 Ω (nlog n) time for trees with n vertices.