Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

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)
What and Who
Title:One-round discrete Voronoi Games
Speaker:Sandor Kisfaludi-Bak
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, SWS
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 26 November 2019
Duration:30 Minutes
Building:E1 4
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
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Stefano Leucci, 11/26/2019 01:51 PM
  • Stefano Leucci, 11/21/2019 09:48 AM
  • Stefano Leucci, 11/08/2019 04:08 PM -- Created document.