Name
Abstract | ||
|---|---|---|
The classical Erdos-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 Erdos-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 Erdos-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. |
Year | Venue | Keywords |
|---|---|---|
2012 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | Erdos-Szekeres problem,Ramsey theory,convex k-gon,empty convex k-gon |
DocType | Volume | Issue |
Journal | 15.0 | 3.0 |
ISSN | Citations | PageRank |
1462-7264 | 0 | 0.34 |
References | Authors | |
4 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Parikshit Kolipaka | 1 | 0 | 0.34 |
| Sathish Govindarajan | 2 | 110 | 12.84 |