dc.contributor.advisor Govindarajan, Sathish dc.contributor.author Parikshit, K dc.date.accessioned 2014-08-01T09:43:03Z dc.date.accessioned 2018-07-31T04:38:29Z dc.date.available 2014-08-01T09:43:03Z dc.date.available 2018-07-31T04:38:29Z dc.date.issued 2014-08-01 dc.date.submitted 2011 dc.identifier.uri https://etd.iisc.ac.in/handle/2005/2352 dc.identifier.abstract http://etd.iisc.ac.in/static/etd/abstracts/3025/G24686-Abs.pdf en_US dc.description.abstract The following problem has been known for its beauty and elementary character. The Erd˝os Szekeres problem[7]: en_US 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. dc.language.iso en_US en_US dc.relation.ispartofseries G24686 en_US dc.subject Game Theory en_US dc.subject Erdos Szekeres Problem en_US dc.subject Convex 5-Gon Game en_US dc.subject Empty Convex 5-Gon Game en_US dc.subject Erdos Szekeres Problem - Game Variants en_US dc.subject.classification Computer Science en_US dc.title Two Player Game Variant Of The Erdos Szekeres Problem en_US dc.type Thesis en_US dc.degree.name MSc Engg en_US dc.degree.level Masters en_US dc.degree.discipline Faculty of Engineering en_US
﻿