The Inverse Voronoi Problem in Graphs II: Trees
- PDF / 2,943,885 Bytes
- 36 Pages / 439.37 x 666.142 pts Page_size
- 23 Downloads / 239 Views
The Inverse Voronoi Problem in Graphs II: Trees Édouard Bonnet1 · Sergio Cabello2,5 · Bojan Mohar3 · Hebert Pérez‑Rosés4 Received: 25 February 2019 / Accepted: 28 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We consider the inverse Voronoi diagram problem in trees: given a tree T with positive edge-lengths and a collection 𝕌 of subsets of vertices of V(T), decide whether 𝕌 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 log2 n) time, where n is the number of vertices in ∑ T and N = n + 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. Keywords Voronoi diagram in graphs · Inverse Voronoi problem · Trees · Applications of binary search trees · Dynamic programming in trees · Lower bounds
1 Introduction Let T be a tree with n vertices and abstract, positive edge-lengths 𝜆 ∶ E(T) → ℝ>0 . The length of a path in T is the sum of the edge-lengths along the path. The (shortest-path) distance between two vertices x and y of T, denoted by dT (x, y) , is the length of the unique path in T from x to y. Let Σ be a subset of V(T). We refer to each element of Σ as a site, to distinguish it from an arbitrary vertex of T. The Voronoi cell of each site s ∈ Σ is then defined by * Sergio Cabello [email protected]‑lj.si Édouard Bonnet edouard.bonnet@ens‑lyon.fr Bojan Mohar [email protected] 1
Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR, Lyon, France
2
Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia
3
Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada
4
Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Tarragona, Spain
5
IMFM, Ljubljana, Slovenia
13
Vol.:(0123456789)
Algorithmica
cellT (s, Σ) = {x ∈ V(T) ∣ ∀s� ∈ Σ ∶ dT (s, x) ≤ dT (s� , x)}. The Voronoi diagram of Σ in T is
𝕍T (Σ) = {cellT (s, Σ) ∣ s ∈ Σ}. When the tree is clear from the context, we remove the subindex and thus just talk about d( , ) , cell(s, Σ) and 𝕍 (Σ) . It is easy to see that, for each set Σ of sites, each vertex of T belongs to some Voronoi cell. Therefore, the sets in 𝕍T (Σ) cover all vertices of T. On the other hand, the Voronoi cells do not need to be pairwise disjoint. In particular, when some vertex of T is closest to two sites, then it is in both Voronoi cells. In this paper we consider computational aspects of the inverse Voronoi problem in trees. This means that we are given a collection of candidate Voronoi cells in a tree, and we would like to decide whether they form indeed a Voronoi diagram. Let us describe the problem more formally. Graphic Inverse Voronoi in Trees Input: (T, 𝕌) , where T is a tree with positive edge-lengths and 𝕌 = (U1 , … , Uk ) is a sequence of subsets of vertices of T that cover V(T). Question: Are there sites s1 , … , sk ∈ V(T) such that cellT (si , {s1 , … , sk }) = Ui for each i ∈ {1, … , k} ? When t
Data Loading...
