On the Erdos-Szekeres n-interior point problem


Autoria(s): Bharadwaj, Subramanya BV; Govindarajan, Sathish; Sharma, Karmveer
Data(s)

01/12/2011

Resumo

The n-interior point variant of the Erdos-Szekeres problem is to show the following: For any n, n-1, every point set in the plane with sufficient number of interior points contains a convex polygon containing exactly n-interior points. This has been proved only for n-3. In this paper, we prove it for pointsets having atmost logarithmic number of convex layers. We also show that any pointset containing atleast n interior points, there exists a 2-convex polygon that contains exactly n-interior points.

Formato

application/pdf

Identificador

http://eprints.iisc.ernet.in/46029/1/Elec_Not_Dis_Math_30_135_2011.pdf

Bharadwaj, Subramanya BV and Govindarajan, Sathish and Sharma, Karmveer (2011) On the Erdos-Szekeres n-interior point problem. In: The Sixth European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2011, 2001, EuroComb.

Publicador

Elsevier Science

Relação

http://dx.doi.org/10.1016/j.endm.2011.09.023

http://eprints.iisc.ernet.in/46029/

Palavras-Chave #Computer Science & Automation (Formerly, School of Automation)
Tipo

Conference Paper

PeerReviewed