de Berg, Mark ;
KisfaludiBak, Sándor ;
Mehr, Mehran
On OneRound Discrete Voronoi Games
Abstract
Let V be a multiset of n points in R^d, which we call voters, and let k >=slant 1 and l >=slant 1 be two given constants. We consider the following game, where two players P and Q compete over the voters in V: First, player P selects a set P of k points in R^d, and then player Q selects a set Q of l points in R^d. Player P wins a voter v in V iff dist(v,P) <=slant dist(v,Q), where dist(v,P) := min_{p in P} dist(v,p) and dist(v,Q) is defined similarly. Player P wins the game if he wins at least half the voters. The algorithmic problem we study is the following: given V, k, and l, how efficiently can we decide if player P has a winning strategy, that is, if P can select his k points such that he wins the game no matter where Q places her points.
Banik et al. devised a singlyexponential algorithm for the game in R^1, for the case k=l. We improve their result by presenting the first polynomialtime algorithm for the game in R^1. Our algorithm can handle arbitrary values of k and l. We also show that if d >= 2, deciding if player P has a winning strategy is Sigma_2^Phard when k and l are part of the input. Finally, we prove that for any dimension d, the problem is contained in the complexity class exists for all R, and we give an algorithm that works in polynomial time for fixed k and l.
BibTeX  Entry
@InProceedings{deberg_et_al:LIPIcs:2019:11533,
author = {Mark de Berg and S{\'a}ndor KisfaludiBak and Mehran Mehr},
title = {{On OneRound Discrete Voronoi Games}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {37:137:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11533},
URN = {urn:nbn:de:0030drops115339},
doi = {10.4230/LIPIcs.ISAAC.2019.37},
annote = {Keywords: competitive facility location, plurality point}
}
28.11.2019
Keywords: 

competitive facility location, plurality point 
Seminar: 

30th International Symposium on Algorithms and Computation (ISAAC 2019)

Issue date: 

2019 
Date of publication: 

28.11.2019 