The Inverse Voronoi Problem in Graphs I: Hardness
- PDF / 3,149,840 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 50 Downloads / 171 Views
The Inverse Voronoi Problem in Graphs I: Hardness Édouard Bonnet1 · Sergio Cabello2,3 · Bojan Mohar4 · Hebert Pérez‑Rosés5 Received: 25 February 2019 / Accepted: 20 April 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We introduce the inverse Voronoi diagram problem in graphs: given a graph G with positive edge-lengths and a collection 𝕌 of subsets of vertices of V(G), decide whether 𝕌 is a Voronoi diagram in G with respect to the shortest-path metric. We show that the problem is NP-hard, even for planar graphs where all the edges have unit length. We also study the parameterized complexity of the problem and show that the problem is W[1]-hard when parameterized by the number of Voronoi cells or by the pathwidth of the graph. Keywords Distances in graphs · Voronoi diagram · Inverse Voronoi problem · NP-complete · Parameterized complexity Bojan Mohar: On leave from IMFM & FMF, Department of Mathematics, University of Ljubljana. É. Bonnet: Supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). S. Cabello: Supported by the Slovenian Research Agency, program P1-0297 and projects J1-1693, J1-8130, J1-8155, J1-9109. B. Mohar: Supported in part by the NSERC Discovery Grant R611450 (Canada), by the Canada Research Chairs program, and by the Research Project J1-8130 of ARRS (Slovenia). H. Pérez-Rosés: Partially supported by Grant MTM2017-86767-R from the Spanish Ministry of Economy, Industry and Competitiveness. * Sergio Cabello [email protected]‑lj.si Édouard Bonnet edouard.bonnet@ens‑lyon.fr Bojan Mohar [email protected] 1
LIP UMR5668, CNRS, ENS de Lyon, Univ Lyon, Université Claude Bernard Lyon 1, Lyon, France
2
Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia
3
IMFM, Ljubljana, Slovenia
4
Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada
5
Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Tarragona, Spain
13
Vol.:(0123456789)
Algorithmica
1 Introduction Let (X, d) be a metric space, where d ∶ X × X → ℝ≥0 . Let Σ be a subset of X. We refer to each element of Σ as a site, to distinguish it from an arbitrary point of X. The Voronoi cell of each site s ∈ Σ is then defined by
cell (X,d) (s, Σ) = {x ∈ X ∣ ∀s� ∈ Σ ∶ d(s, x) ≤ d(s� , x)}. The Voronoi diagram of Σ in (X, d) is
𝕍(X,d) (Σ) = { cell (X,d) (s, Σ) ∣ s ∈ Σ}. It is easy to see that, for each set Σ of sites, each element of X belongs to some Voronoi cell cell (X,d) (s, Σ) . Therefore, the sets in 𝕍(X,d) (Σ) cover X. On the other hand, the Voronoi cells do not need to be pairwise disjoint. In particular, when some point x ∈ X is closest to two sites, then it is in both Voronoi cells. In the inverse Voronoi problem, we are given a metric space (X, d) and a sequence X1 , … , Xk of subsets of X that cover X. The task it to decide whether {X1 , … , Xk } is a Voronoi diagram in (X, d). This means
Data Loading...
