Geodesic
More on Planar Point Subsets with a Specified Number of Interior Points
Matematičeskie zametki, Tome 83 (2008) no. 5, pp. 752-756.

Voir la notice de l'article provenant de la source Math-Net.Ru

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer $k\ge1$, let $g(k)$ be the smallest integer such that every set $P$ of points in the plane with no three collinear points and with at least $g(k)$ interior points has a subset containing precisely $k$ interior point of $P$. We prove that $g(k)\ge3k$ for $k\ge3$, which improves the known result that $g(k)\ge3k-1$ for $k\ge3$.
Keywords: interior point of a finite planar set, convex hull, deficient point set. 
@article{MZM_2008_83_5_a10,
     author = {Wei Xiang Lin and Ding Ren},
     title = {More on {Planar} {Point} {Subsets} with a {Specified} {Number} of {Interior} {Points}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {752--756},
     publisher = {mathdoc},
     volume = {83},
     number = {5},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2008_83_5_a10/}
}
TY  - JOUR
AU  - Wei Xiang Lin
AU  - Ding Ren
TI  - More on Planar Point Subsets with a Specified Number of Interior Points
JO  - Matematičeskie zametki
PY  - 2008
SP  - 752
EP  - 756
VL  - 83
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2008_83_5_a10/
LA  - ru
ID  - MZM_2008_83_5_a10
ER  - 
%0 Journal Article
%A Wei Xiang Lin
%A Ding Ren
%T More on Planar Point Subsets with a Specified Number of Interior Points
%J Matematičeskie zametki
%D 2008
%P 752-756
%V 83
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2008_83_5_a10/
%G ru
%F MZM_2008_83_5_a10
Wei Xiang Lin; Ding Ren. More on Planar Point Subsets with a Specified Number of Interior Points. Matematičeskie zametki, Tome 83 (2008) no. 5, pp. 752-756. http://geodesic.mathdoc.fr/item/MZM_2008_83_5_a10/

[1] D. Avis, K. Hosono, M. Urabe, “On the existence of a point subset with a specified number of interior points”, Discrete Math., 241:1–3 (2001), 33–40 | DOI | MR | Zbl

[2] T. Fevens, “A note on point subsets with a specified number of interior points”, Discrete and computational geometry, Lecture Notes in Comput. Sci., 2866, Springer, Berlin, 2003, 152–158 | DOI | MR

[3] P. Erdös, G. Szekeres, “A combinatorial problem in geometry”, Compositio Math., 2 (1935), 463–470 | MR | Zbl

[4] J. Horton, “Sets with no empty $7$-gons”, Canad. Math. Bull., 26:4 (1983), 482–484 | MR | Zbl

[5] K. Hosono, G. Károlyi, M. Urabe, “On the existence of a convex polygon with a specified number of interior points”, Discrete Geometry, In Honor of W. Kuperberg's 60th Birthday, Monogr. Textbooks Pure Appl. Math., 253, Marcel Dekker, New York, 2003, 351–358 | MR | Zbl

[6] T. Bisztriczky, K. Hosono, G. Károlyi, M. Urabe, “Constructions from empty polygons”, Period. Math. Hungar., 49:2 (2004), 1–8 | DOI | MR | Zbl

[7] P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry, Springer, New York, 2005 | MR | Zbl

[8] J. D. Kalbfleisch, J. G. Kalbfleisch, R. G. Santon, “A combinatorial problem on convex $n$-gons”, Proc. Louisiana Conf. on Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, LA, 1970, 180–188 | MR | Zbl

[9] W. Morris, V. Soltan, “The Erdös–Szekeres problem on points in convex position – a survey”, Bull. Amer. Math. Soc. (N.S.), 37:4 (2000), 437–458 | DOI | MR | Zbl