View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

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

        Thumbnail
        View/Open
        Extensions on the Voronoi Game_CutsAndRopes_ICA-3617173.pdf (2.383Mb)
        Publication date
        2016
        Author
        Kolste, B. te
        Metadata
        Show full item record
        Summary
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/24961
        Collections
        • Theses
        Utrecht university logo