Record Details

Two Player Game Variant Of The Erdos Szekeres Problem

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Two Player Game Variant Of The Erdos Szekeres Problem
 
Creator Parikshit, K
 
Subject Game Theory
Erdos Szekeres Problem
Convex 5-Gon Game
Empty Convex 5-Gon Game
Erdos Szekeres Problem - Game Variants
Computer Science
 
Description The following problem has been known for its beauty and elementary character. The Erd˝os Szekeres problem[7]:
For any integer k ≥ 3, determine if there exists a smallest positive integer N(k) such that any set of atleast N(k) points in general position in the plane(i.e no three points are in a line) contains k points that are the vertices of a convex k-gon.
The finiteness of (k)is proved by Erd˝os and Szekeres using Ramsey theory[7].
In 1978, Erd˝os [6] raised a similar question on empty convex k-gon (convex k-gon without out any interior points) and it has been extensively studied[18]. Several other variants like the convex k-gon with specified number interior points[2] and the chromatic variant[5] have been well studied.
In this thesis, we introduce the following two player game variant of the Erd˝os Szekeres problem: Consider a two player game where each player places a point in the plane such that the point set formed will not contain a convex k-gon. The game will end when a convex k-gon is formed and the player who placed the last point loses the game. In our thesis we show a winning strategy forplayer2inthe convex5-gongame and the empty convex5-gongame and argue that the game always ends in the 9th step.
We also give an alternative proof for the statement that any point set containing 10 or more points contains an empty convex 5-gon.
 
Contributor Govindarajan, Sathish
 
Date 2014-08-01T09:43:03Z
2014-08-01T09:43:03Z
2014-08-01
2011-01
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/handle/2005/2352
http://etd.ncsi.iisc.ernet.in/abstracts/3025/G24686-Abs.pdf
 
Language en_US
 
Relation G24686