2026-07-23T03:46:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6984 2024-03-06T10:39:14Z ddc:004 open_access

Minkowski Games Le Roux, Stéphane Pauly, Arno Raskin, Jean-François Control in R^d determinacy polytopic/arbitrary coNP-complete undecidable We introduce and study Minkowski games. In these games, two players take turns to choose positions in R^d based on some rules. Variants include boundedness games, where one player wants to keep the positions bounded (while the other wants to escape to infinity), and safety games, where one player wants to stay within a given set (while the other wants to leave it). We provide some general characterizations of which player can win such games, and explore the computational complexity of the associated decision problems. A natural representation of boundedness games yields coNP-completeness, whereas the safety games are undecidable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stéphane Le Roux and Arno Pauly and Jean-François Raskin 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.50 urn:nbn:de:0030-drops-69849 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.50 eng https://creativecommons.org/licenses/by/3.0/legalcode