Continuous Voronoi Games on Graphs with Multiple Opponents

Abstract

In this thesis, we study the puzzle game Lines—a commercial game developed by Gamious—which is a variant of the one-round Voronoi game on graphs. The game presents the player with a graph with coloured dots on the vertices or edges, corresponding with the moves of all opponents. The player is tasked with placing one or more dots in their own colour on the graph, such that when we calculate the Voronoi diagram using the coloured dots as sites, the union of player-coloured Voronoi cells is largest. We develop an algorithm that calculates all winning placements in O(|V||E||S| · (|V| log |V| + |E|)) time for the simplified problem of placing one point, where |V| is the number of vertices, |E| the number of edges, and |S| the number of existing sites. We then consider the generalised question of placing k sites and we present an algorithm that runs in O(|V|^k |E|^(2k) k^(2k) (|C| + k^2)^k) time, where |C| is the number of different colours of the sites. Finally, we discuss further generalisations and extensions.