The Voronoi game on graphs and its complexity
The Voronoi game is a two-person game which is a model for a competitive facility location. The game is played on a continuous domain, and only two special cases (one-dimensional case and one-round case) are well investigated. We introduce the discrete Voronoi game in which the game arena is given a...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Journal of Graph Algorithms and Applications
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121515 |
| _version_ | 1811084986214776832 |
|---|---|
| author | Teramoto, Sachio Demaine, Erik D Uehara, Ryuhei |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Teramoto, Sachio Demaine, Erik D Uehara, Ryuhei |
| author_sort | Teramoto, Sachio |
| collection | MIT |
| description | The Voronoi game is a two-person game which is a model for a competitive facility location. The game is played on a continuous domain, and only two special cases (one-dimensional case and one-round case) are well investigated. We introduce the discrete Voronoi game in which the game arena is given as a graph. We first analyze the game when the arena is a large complete k-ary tree, and give an optimal strategy. When both players play optimally, the first player wins when k is odd, and the game ends in a tie for even k. Next we show that the discrete Voronoi game is intractable in general. Even for the one-round case in which the strategy adopted by the first player consist of a fixed single node, deciding whether the second player can win is NP-complete. We also show that deciding whether the second player can win is PSPACE-complete in general. |
| first_indexed | 2024-09-23T13:01:10Z |
| format | Article |
| id | mit-1721.1/121515 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:01:10Z |
| publishDate | 2019 |
| publisher | Journal of Graph Algorithms and Applications |
| record_format | dspace |
| spelling | mit-1721.1/1215152022-10-01T12:34:01Z The Voronoi game on graphs and its complexity Teramoto, Sachio Demaine, Erik D Uehara, Ryuhei Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science The Voronoi game is a two-person game which is a model for a competitive facility location. The game is played on a continuous domain, and only two special cases (one-dimensional case and one-round case) are well investigated. We introduce the discrete Voronoi game in which the game arena is given as a graph. We first analyze the game when the arena is a large complete k-ary tree, and give an optimal strategy. When both players play optimally, the first player wins when k is odd, and the game ends in a tie for even k. Next we show that the discrete Voronoi game is intractable in general. Even for the one-round case in which the strategy adopted by the first player consist of a fixed single node, deciding whether the second player can win is NP-complete. We also show that deciding whether the second player can win is PSPACE-complete in general. 2019-07-08T16:07:17Z 2019-07-08T16:07:17Z 2011-08 2011-07 2019-06-19T14:36:26Z Article http://purl.org/eprint/type/JournalArticle 1526-1719 https://hdl.handle.net/1721.1/121515 Teramoto, Sachio et al. "The Voronoi game on graphs and its complexity." Journal of Graph Algorithms and Applications 15, 4 (August 2011): 485-501 © 2011 Journal of Graph Algorithms and Applications en http://dx.doi.org/10.7155/jgaa.00235 Journal of Graph Algorithms and Applications Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Journal of Graph Algorithms and Applications Other repository |
| spellingShingle | Teramoto, Sachio Demaine, Erik D Uehara, Ryuhei The Voronoi game on graphs and its complexity |
| title | The Voronoi game on graphs and its complexity |
| title_full | The Voronoi game on graphs and its complexity |
| title_fullStr | The Voronoi game on graphs and its complexity |
| title_full_unstemmed | The Voronoi game on graphs and its complexity |
| title_short | The Voronoi game on graphs and its complexity |
| title_sort | voronoi game on graphs and its complexity |
| url | https://hdl.handle.net/1721.1/121515 |
| work_keys_str_mv | AT teramotosachio thevoronoigameongraphsanditscomplexity AT demaineerikd thevoronoigameongraphsanditscomplexity AT uehararyuhei thevoronoigameongraphsanditscomplexity AT teramotosachio voronoigameongraphsanditscomplexity AT demaineerikd voronoigameongraphsanditscomplexity AT uehararyuhei voronoigameongraphsanditscomplexity |