On One-Round Discrete Voronoi Games

Let V be a multiset of n points in ℝd, which we call voters, and let k≥ 1 and ℓ≥ 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 k points in ℝd, and then player Q selects ℓ points in ℝd. Player P wins a voter v∈ V iff dist(v,P) ≤ dist(v,Q), where dist(v,P) := minp∈ 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 ℓ, 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 ℝ1, for the case k=ℓ. We improve their result by presenting the first polynomial-time algorithm for the game in ℝ1. Our algorithm can handle arbitrary values of k and ℓ. We also show that if d≥ 2, deciding if player P has a winning strategy is Sigma2P-hard when k and ℓ are part of the input. Finally, we prove that for any dimension d, the problem is contained in the complexity class existsforall ℝ, and we give an algorithm that works in polynomial time for fixed k and ℓ.