Name
Abstract | ||
|---|---|---|
The n-interior-point variant of the Erdos-Szekeres problem is the following: for every n,n=1, does there exist a g(n) such that every point set in the plane with at least g(n) interior points has a convex polygon containing exactly n interior points. The existence of g(n) has been proved only for n@?3. In this paper, we show that for any fixed r=2, and for every n=5, every point set having sufficiently large number of interior points and at most r convex layers contains a subset with exactly n interior points. We also consider a relaxation of the notion of convex polygons and show that for every n,n=1, any point set with at least n interior points has an almost convex polygon (a simple polygon with at most one concave vertex) that contains exactly n interior points. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.ejc.2013.06.028 | Eur. J. Comb. |
Keywords | DocType | Volume |
n-interior-point variant,fixed r,interior point,concave vertex,s-szekeres n-interior-point problem,n interior point,large number,erdos-szekeres problem,convex polygon,r convex layer,simple polygon | Journal | 35, |
ISSN | Citations | PageRank |
0195-6698 | 0 | 0.34 |
References | Authors | |
8 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| B.V. Subramanya Bharadwaj | 1 | 5 | 1.45 |
| Sathish Govindarajan | 2 | 110 | 12.84 |
| Karmveer Sharma | 3 | 0 | 0.34 |