On one-round discrete voronoi games

Mark T. de Berg, Sándor Kisfaludi-Bak, Mehran Mehr

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

4 Downloads (Pure)


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 singly-exponential algorithm for the game in R^1, for the case k=l. We improve their result by presenting the first polynomial-time 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^P-hard 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.
Originele taal-2Engels
Titel30th International Symposium on Algorithms and Computation, ISAAC 2019
RedacteurenPinyan Lu, Guochuan Zhang
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's17
ISBN van elektronische versie978-3-95977-130-6
StatusGepubliceerd - dec 2019
Evenement30th International Symposium on Algorithms and Computation - 1st Floor at SUFE Research Lab Center, No.100 Wudong Road, Shanghai, China
Duur: 9 dec 201911 dec 2019

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
ISSN van geprinte versie1868-8969


Congres30th International Symposium on Algorithms and Computation
Verkorte titelISAAC 2019
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'On one-round discrete voronoi games'. Samen vormen ze een unieke vingerafdruk.

Citeer dit