max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 New for: D1
 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: One-round discrete Voronoi Games Sandor Kisfaludi-Bak Max-Planck-Institut für Informatik - D1 AG1 Mittagsseminar (own work) D1, SWSWe use this to send out email in the morning. AG Audience English
Date: Tuesday, 26 November 2019 13:00 30 Minutes Saarbrücken E1 4 024
 Let V be a multiset of n points in d-dimensinal Euclidean space, which 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.
Name(s): Stefano Leucci