Erdos-Szekeres-Type Games

Oswin Aichholzer; José Miguel Díaz-Báñez; Thomas Hackl; David Orden Martín; Alexander Pilz; Inmaculada Ventura; Birgit Vogtenhuber

Erdos-Szekeres-Type Games

Oswin Aichholzer, José Miguel Díaz-Báñez, Thomas Hackl, David Orden Martín, Alexander Pilz, Inmaculada Ventura, Birgit Vogtenhuber

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

Abstract

We consider several combinatorial games, inspired by the Erdos-Szekeres theorem that states the existence of a convex $k$-gon in every sufficiently large point set. Two players take turns to place points in the Euclidean plane and the game is over as soon as the first $k$-gon appears. In the Maker-Maker setting the player who placed the last point wins, while in the Avoider-Avoider version this player loses. Combined versions like Maker-Breaker are also possible. Moreover, variants can be obtained by considering that (1) the points to be placed are either uncolored or bichromatic, (2) both players have their own color or can play with both colors, (3) the $k$-gon must be empty of other points, or (4) the $k$-gon has to be convex.

Originalsprache	englisch
Titel	Proc. $35^th$ European Workshop on Computational Geometry EuroCG '19
Erscheinungsort	Utrecht, The Netherlands
Seiten	23:1-23:7
Publikationsstatus	Veröffentlicht - 2019

Fields of Expertise

Information, Communication & Computing

Zugriff auf Dokument

http://www.eurocg2019.uu.nl/papers/23.pdf

Dieses zitieren

@inproceedings{ba95e0935dea4075a5ceb3a2cf8e7f2a,

title = "Erdos-Szekeres-Type Games",

abstract = "We consider several combinatorial games, inspired by the Erdos-Szekeres theorem that states the existence of a convex $k$-gon in every sufficiently large point set. Two players take turns to place points in the Euclidean plane and the game is over as soon as the first $k$-gon appears. In the Maker-Maker setting the player who placed the last point wins, while in the Avoider-Avoider version this player loses. Combined versions like Maker-Breaker are also possible. Moreover, variants can be obtained by considering that (1) the points to be placed are either uncolored or bichromatic, (2) both players have their own color or can play with both colors, (3) the $k$-gon must be empty of other points, or (4) the $k$-gon has to be convex.",

author = "Oswin Aichholzer and D{\'i}az-B{\'a}{\~n}ez, {Jos{\'e} Miguel} and Thomas Hackl and {Orden Mart{\'i}n}, David and Alexander Pilz and Inmaculada Ventura and Birgit Vogtenhuber",

year = "2019",

language = "English",

pages = "23:1--23:7",

booktitle = "Proc. $35^th$ European Workshop on Computational Geometry EuroCG '19",

}

TY - GEN

T1 - Erdos-Szekeres-Type Games

AU - Aichholzer, Oswin

AU - Díaz-Báñez, José Miguel

AU - Hackl, Thomas

AU - Orden Martín, David

AU - Pilz, Alexander

AU - Ventura, Inmaculada

AU - Vogtenhuber, Birgit

PY - 2019

Y1 - 2019

N2 - We consider several combinatorial games, inspired by the Erdos-Szekeres theorem that states the existence of a convex $k$-gon in every sufficiently large point set. Two players take turns to place points in the Euclidean plane and the game is over as soon as the first $k$-gon appears. In the Maker-Maker setting the player who placed the last point wins, while in the Avoider-Avoider version this player loses. Combined versions like Maker-Breaker are also possible. Moreover, variants can be obtained by considering that (1) the points to be placed are either uncolored or bichromatic, (2) both players have their own color or can play with both colors, (3) the $k$-gon must be empty of other points, or (4) the $k$-gon has to be convex.

AB - We consider several combinatorial games, inspired by the Erdos-Szekeres theorem that states the existence of a convex $k$-gon in every sufficiently large point set. Two players take turns to place points in the Euclidean plane and the game is over as soon as the first $k$-gon appears. In the Maker-Maker setting the player who placed the last point wins, while in the Avoider-Avoider version this player loses. Combined versions like Maker-Breaker are also possible. Moreover, variants can be obtained by considering that (1) the points to be placed are either uncolored or bichromatic, (2) both players have their own color or can play with both colors, (3) the $k$-gon must be empty of other points, or (4) the $k$-gon has to be convex.

M3 - Conference paper

SP - 23:1-23:7

BT - Proc. $35^th$ European Workshop on Computational Geometry EuroCG '19

CY - Utrecht, The Netherlands

ER -