One-round discrete Voronoi Games

we call voters, and let k and l be two given numbers. We consider the
following game, where two players P and Q compete over the voters in V:
First, player P selects a set of k points, then player Q selects a set
of l points. A player wins a voter v iff one of their points is closer
to v than all points of the other player, and a player wins the game if
they win at least half the voters. Given V, k and l, how efficiently can
we decide if player P has a winning strategy? Banik et al. devised a
singly-exponential algorithm for the game on the line. I will sketch our
polynomial-time algorithm for this problem, which is essentially an
undiscretized dynamic program. Then I will briefly talk about the
problem in higher dimensions d>=2, where deciding if player P has a
winning strategy is hard for the second level of the polynomial
hierarchy (if k and l are part of the input). In the end, I will talk
about our algorithm that works in polynomial time for fixed d, k, and l.
The talk is based on joint work with Mark de Berg and Mehran Mehr.