Computational Geometry Seminar: Marc van Kreveld

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.