On one-round discrete voronoi games

Let V be a multiset of n points in Rd, 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 Rd, and then player Q selects ℓ points in Rd. Player P wins a voter v∈V iff dist(v,P)≤dist(v,Q), where dist(v,P):=minp∈Pdist(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 R1, for the case k=ℓ. We improve their result by presenting the first polynomial-time algorithm for the game in R1. 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 ΣP2-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 ∃∀R, and we give an algorithm that works in polynomial time for fixed k and ℓ