• https://mat.upc.edu/ca/activitats/computational-geometry-seminar-marc-van-kreveld
• Computational Geometry Seminar: Marc van Kreveld
• 2016-11-12T12:30:00+01:00
• 2016-11-12T13:30:00+01:00
• Title: The Pokémon GO search problem and its competitive analysis. Speaker: Marc van Kreveld, Utrecht University (http://www.staff.science.uu.nl/~kreve101/)

Title: The Pokémon GO search problem and its competitive analysis. Speaker: Marc van Kreveld, Utrecht University (http://www.staff.science.uu.nl/~kreve101/)

Quan

12/11/2016 de 12:30 a 13:30

On

Room S215 Omega Building, Campus Nord UPC (equiv.: Room 215 Floor -2)

Afegeix un esdeveniment al calendari

iCal

Abstract: After its introduction in the summer of 2016, Pokémon GO quickly became the most popular game around. The game requires players---called trainers---to walk outside to search for and catch Pokémon. Now that the first craze is over, it is time for scientists to analyze various aspects of the game. Since the game requires a mobile device with GPS and is (in part) essentially a search problem played on the streets, we can analyze it using competitive analysis. We define an abstraction of searching for Pokémon using a geometric graph and call it the Pokémon GO search problem. We show that for general geometric graphs, there is no constant competitive ratio to find a Pokémon. However, if the graph has convex faces only, or if the graph has constant-bounded geometric dilation, then there is an O(1)-competitive search strategy.