Extensions on the Continuous Voronoi game on Graphs: cuts & ropes

Abstract

We study a puzzle game called Lines developed by Gamious. The game is a variant of the Continuous Voronoi game on graphs. The player is presented a graph containing sites and is tasked to alter the graph either by cutting an edge or adding an edge (Rope). The graph is then subdivided according to the closest sites, and the player who controls the most area on the graph wins.

We present an algorithm to find the best cut for arbitrary graphs in O(|E|\cdot(|V|+|E|)) time, where |E| is the number of edges and |V| is the number of vertices. For trees we present two algorithms; one runs in O(|V||S| log Delta(G)) time and one runs in O(d |V| log |S| log Delta(G)) time, where d is the diameter of the graph, |S| is the number of sites in the graph and Delta(G) is the maximum degree in the graph.

Finally, we made a start for ropes and laid out future research.