Parikshit Kolipaka ; Sathish Govindarajan - Two player game variant of the Erdős-Szekeres problem

dmtcs:620 - Discrete Mathematics & Theoretical Computer Science, November 6, 2013, Vol. 15 no. 3 - https://doi.org/10.46298/dmtcs.620
Two player game variant of the Erdős-Szekeres problemArticle

Authors: Parikshit Kolipaka 1; Sathish Govindarajan 1

  • 1 Department of Computer Science and Automation [Bangalore]

The classical Erd˝os-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erd˝os-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdös-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations


Volume: Vol. 15 no. 3
Section: Combinatorics
Published on: November 6, 2013
Accepted on: June 9, 2015
Submitted on: September 19, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 681 times.
This article's PDF has been downloaded 559 times.