# On the Existence of a Point Subset with 3 or 6 Interior Points

Authors: Banyat Sroysang
Journal: ISRN Geometry
 (2013)

---

## Abstract

For any finite planar point setP
in general position, an interior point of the set P
is a point of the set P
such that it is not on the boundary of the convex hull of the set P. For any positive integer k≥3, let h(k) be the smallest integer such that every finite planar point set P with no three collinear points and with at least h(k)
interior points has a subset Q for which the interior of the convex hull of the set Q
contains exactly k
or k+3
interior points of the set P. In this paper, we prove that h(3)=8.


---

## Body

## 1. Introduction

In this paper, we focus on finite planar point sets in general position; that is, no three points are collinear. In 1935, Erdős and Szekeres [1] posed a problem: for any integer k≥3, determine the smallest positive integer f(k) such that any finite point set of at least f(k) points has a subset of k points whose convex hull contains exactly k vertices. In 1961, they [2] showed that f(k)≥2k-2+1 for all integer k≥3 and then conjectured that f(k)≥2k-2+1 for all integer k≥3. In 1974, Bonnice [3] proved that f(3)=3 and f(4)=5. In 1970, Kalbfleisch et al. [4] showed that f(5)=9. In 2006, the computer solution for k=6 was presented by Szekeres and Peters [5]; that, f(6)=17.In 2001, Avis et al. [6] posed an interior point problem: for any integer k≥1, determine the smallest positive integer g(k) such that any finite point set P of at least g(k) points has a subset Q for which the interior of the convex hull of the set Q contains exactly k points in the set P. Moreover, they also showed the results that g(1)=1 and g(2)=4. In 1974, Bonnice [3] showed that g(k)≥3k-1 for all integer k≥3. In 2008, Wei and Ding [7] showed that g(k)≥3k for all integer k≥3. Moreover, in 2009, they [8] also showed that g(3)=9. In 2011, Sroysang [9] showed that g(k)≥4k for all integer k≥4. Moreover, in 2012, he [10] also showed that g(k)≥k2 for all integer k≥4.In 2001, Avis et al. [6] proved that 3 is the smallest positive integer such that any finite point set P of at least 3 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 or 4 points in the set P. Moreover, they [11] also proved that 7 is the smallest positive integer such that any finite point set P of at least 7 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 4 or 5 points in the set P. In 2009, Wei and Ding [12] showed that any planar point set P with 3 vertices and 9 interior points has a subset with 5 or 6 interior points of the set P.In 2010, Wei et al. [13] proved that 8 is the smallest positive integer such that any finite point set P of at least 8 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 or 5 points in the set P.In 2012, Sroysang [14] proved that 7 is the smallest positive integer such that any finite point set P of at least 7 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 or 7 points in the set P.In this paper, we pose an interior point problem: for any integerk≥3, determine the smallest positive integer h(k) such that any finite point set P of at least h(k) points has a subset Q for which the interior of the convex hull of the set Q contains exactly k or k+3 points in the set P. We show that h(3)=8; that is, 8 is the smallest positive integer such that any finite point set P of at least 8 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 or 6 points in the set P.


## 2. Preliminaries

In this section, we list propositions and notations about the setP, where P is a finite planar point set such that no three points are collinear.Aninterior point of the set P is a point of the set P such that it is not on the boundary of the convex hull of the set P.We denote notations as follows:I(P)≔ the set of interior points of the set P,i(P)≔ the number of elements in the set I(P),CH(P)≔ the convex hull of the set P,intCH(P)≔ the interior of the set CH(P),V(P)≔ the set of vertices of the set CH(P),v(P)≔ the number of elements in the set V(P).ForQ⊆P,I*(Q)≔I(P)∩intCH(Q),i*(Q)≔ the number of elements in the set I*(Q).Forx,y,z∈P,Δxyz≔ the triangle with vertices x, y, and z.Anedge of the set P is an edge in CH(P). A subset Q of the set P is called a k-int subset if i*(Q)=k.Note that there isQ⊆P such that i(Q)≠i*(Q).Proposition 1 (see [8]).
9 is the smallest integer such that any finite point setP of at least 9 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 points in the set P.For any positive integerk≥3, we let h(k) be the smallest integer such that every planar point set P with no three collinear points and with at least h(k) interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly k or k+3 points of the set P.For any positive integerk≥3,
(1)h(k)=min{s:i(P)≥s⟹∃Q⊆Ps.t.i*(Q)=kork+3}A finite planar point setP is called a deficient point set of typeP(m,s,k,n) and denoted by P=P(m,s,k,n) if v(P)=m,i(P)=s, and i*(Q)∉{k,n} for all Q⊆P.An edgexy of the set P(3,s,3,3) is of typek if there exists a subset Q of the set P with i*(Q)=k such that the edge xy is an edge of the set Q.Proposition 2 (see [8]).
Every edge of a deficient point set of typeP(3,7,3,3) is of type 2.


## 3. Main Results

In this section, we will show that 8 is the smallest positive integer such that any finite point setP of at least 8 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 or 6 points in the set P.Lemma 3.
h
(
3
)
≤
9.Proof.
LetP be a finite planar point set such that i(P)≥9.
By Proposition1, there is a subset Q of the set P such that i*(Q)=3. Then i*(Q)∈{3,6}. Hence, h(3)≤9.Lemma 4.
h
(
3
)
≥
8.Proof.
This suffices to show the existence of a deficient point set of typeP(3,7,3,6). We construct a deficient point set P of type P(3,7,3,6) as shown in Figure 1. Hence, h(3)≥8.Figure 1
A deficient point set of typeP(3,7,3,6).Lemma 5.
LetP be a finite planar point set. Assume that v(P)=3 and i(P)=8. Then the set P has a 3-int or 6-int subset.Proof.
Suppose that each subset of a planar point setP is not a 3-int subset. In [8], we have only three different configurations of the type P(3,8,3,3) as shown in Figures 2, 3, and 4. However, each configuration has a subset Q for which the interior of the convex hull of the set Q contains exactly 6 points of the set P. Hence, the set P has a 3-int or 6-int subset.Figure 2
8-I-monster.Figure 3
8-II-monster.Figure 4
8-III-monster.Lemma 6.
LetP be a finite planar point set. Assume that v(P)=4 and i(P)=8. Then the set P has a 3-int or 6-int subset.Proof.
LetV(P)={x,y,z,andw} be such that vertices x,y,z,w are put into counterclockwise positions, respectively (see Figure 5).
Suppose that each subset of the planar point setP is not a 6-int subset. Then the sets Δxyz, Δyzw, Δzwx, and Δwxy are not 6-int subsets.
IfΔxyz is a 2-int subset, then the set Δzwx is a 6-int subset. Then the set Δxyz is not a 2-int subset. Similarly, the sets Δyzw, Δzwx, and Δwxy are not 2-int subsets.
LetT={Δxyz,Δyzw,Δzwx,Δwxy}.
To show that the setP has a 3-int subset, we divide into seven cases.
Case  1. There is an element A in the set T such that the set A is a 3-int subset.
In this case, the setP has a 3-int subset.
Case  2. There is an element A in the set T such that the set A is a 5-int subset.
Without loss of generality, we assume thatA=Δxyz. Then the set Δzwx is a 3-int subset. Thus, the set P has a 3-int subset.
Case  3. There is an element A in the set T such that the set A is a 7-int subset.
Without loss of generality, we assume thatA=Δxyz. Then the set Δzwx is a 1-int subset. If the set A has a 3-int subset, then the set P has a 3-int subset. Assume that the set A is a deficient point set of type P(3,7,3,3). By Proposition 2, there is a subset B of the set CH(Δxyz) with i*(B)=2 such that the edge xz is an edge of the set B. Let Q=B∪Δzwx. Then i*(Q)=3. Thus, the set P has a 3-int subset.
Case  4. There is an element A in the set T such that the set A is a 1-int subset.
Without loss of generality, we assume thatA=Δxyz. Then the set Δzwx is a 7-int subset. Similar to Case 3, the set P has a 3-int subset.
Case  5. There is an element A in the set T such that the set A is an 8-int subset.
By Lemma5, the set P has a 3-int subset.
Case  6. There is an element A in the set T such that the set A is a 0-int subset.
Without loss of generality, we assume thatA=Δxyz. Then the set Δzwx is an 8-int subset. By Lemma 5, the set P has a 3-int subset.
Case  7. The sets Δxyz, Δyzw, Δzwx, and Δwxy are 4-int subsets.
If one of them has a 3-int subset, then the setP has a 3-int subset. Assume that they are deficient point sets without a 3-int subset. If the edge xz of the set Δxyz is of type 2, then we obtain that i*(P∖{y})=6. It follows that, the edge xz of the set Δxyz is of type 0 or type 1. If the edge xz of the set Δxyz is of type 0, then the edge xy of the set Δxyz is of type 3, so the set P has a 3-int subset. Next, we will assume that the edge xz of the set Δxyz is of type 1. Similarly, it suffices to assume that the edge xz of the set Δzwx is only of type 1, the edge yw of the set Δyzw is only of type 1, and the edge yw of the set Δwxy is only of type 1. Hence, we obtain only one possible configuration as shown in Figure 6.
However, there is a subsetQ of P such that i*(Q)=3, as shown in Figure 7. Thus, the set P has a 3-int subset.
Therefore, the setP has a 3-int or 6-int subset. This proof is completed.Figure 5
Verticesx, y, and z, w are put into counterclockwise positions.Figure 6
The edgesxz and yw are only of type 1.Figure 7
A 3-int subset of the set in Figure6.Lemma 7.
LetP be a finite planar point set. Assume that v(P)≥5 and i(P)=8. Then the set P has a 3-int or 6-int subset.Proof.
Letv(P)=m and V(P)={v1,v2,…,vm} be such that vertices v1,v2,…,vm are put into counterclockwise positions, respectively (see in Figure 8).
Suppose that each subset of the setP is not a 6-int subset. Then the set Δv1vjvj+1 is not a 6-int subset for all j.
LetT={Δv1vjvj+1∣j=2,3,…,m}.
To show that the setP has a 3-int subset, we divide into six cases.
Case  1. There is an element A in the set T such that the set A is a 3-int subset.
In this case, the setP has a 3-int subset.
Case  2. There is an element A in the set T such that the set A is a 7-int subset.
Then the setΔv1vtvt+1 is a 1-int subset for some t. Without loss of generality, we assume A=Δv1vjvj+1 for some j>t. If the set A has a 3-int subset, then the set P has a 3-int subset. Assume that the set A is a deficient point set of type P(3,7,3,3). By Proposition 2, there is a subset B of the set CH(A) with i*(B)=2 such that the edge v1vj is an edge of the set B. Let Q=B∪Δv1vtvt+1. Then i*(Q)=3. Thus, the set P has a 3-int subset.
Case  3. There is an element A in the set T such that the set A is a 5-int subset.
We divide into three subcases.
Subcase  3.1. There is an element B in the set T such that the set B is a 3-int subset.
In this subcase, the setP has a 3-int subset.
Subcase  3.2. There exist elements B, C, and D in the set T such that the sets B, C, and D are 1-int subsets.
It follows thatA=Δv1vjvj+1, B=Δv1vtvt+1, C=Δv1vsvs+1, and D=Δv1vrvr+1, where j,t,s,r∈{2,3,…,m}. Without loss of generality, we assume that |t-j|=min{|t-j|,|s-j|,|r-j|}. Then the set A∪B is a 6-int subset. This is impossible.
Subcase  3.3. There exist elements B, C in the set T such that the set B is a 1-int subset and the set C is a 2-int subset.
It follows thatA=Δv1vjvj+1, B=Δv1vtvt+1 and C=Δv1vrvr+1 where j,t,r∈{2,3,…,m}. If r is not between t and j, then the set A∪B is a 6-int subset which is impossible. Thus, r is between t and j. We choose Q=B∪C. Then i*(Q)=3. Hence, the set P has a 3-int subset.
Case  4. There is an element A in the set T such that the set A is a 4-int subset.
We divide into five subcases.
Subcase  4.1. There is an element B in the set T such that the set B is a 3-int subset.
In this subcase, the setP has a 3-int subset.
Subcase  4.2. There exist elements B, C, D, and E in the set T such that the sets B, C, D, and E are 1-int subsets.
It follows thatA=Δv1vjvj+1, B=Δv1vtvt+1, C=Δv1vsvs+1, D=Δv1vkvk+1, and E=Δv1vrvr+1, where j, t, s, r, k∈{2,3,…,m}. Without loss of generality, we can assume that t<s<k<r. If j<s, then the set C∪D∪E is a 3-int subset. If k<j, then the set B∪C∪D is a 3-int subset. Thus, the set P has a 3-int subset if j<s or k<j. Next, we will show that the statement “s<j<k” is impossible. We suppose that s<j<k. Then the set A∪C∪D is a 6-int subset which is a contradiction.
Subcase  4.3. There exist elements B and C in the set T such that the sets B and C are 2-int subsets.
It follows thatA=Δv1vjvj+1, B=Δv1vtvt+1and C=Δv1vrvr+1 where j,t,r∈{2,3,…,m}. Without loss of generality, we assume |t-j|<|r-j|. Then the set A∪B is a 6-int subset. This is impossible.
Subcase  4.4. There exist elements B, C, and D in the set T such that the sets B and C are 1-int subsets and the set D is a 2-int subset.
It follows thatA=Δv1vjvj+1, B=Δv1vtvt+1, C=Δv1vsvs+1, and D=Δv1vrvr+1, where j,t,s,r∈  {2,3,…,m}. Without loss of generality, we can assume that j<r. Let k=max{t,s} and l=min{t,s}. If k<r, then the set A∪B∪C is a 6-int subset. If r<l, then the set A∪D is a 6-int subset. Thus, we obtain that l<r<k. Then the set D∪Δv1vkvk+1 is a 3-int subset. Hence, the set P has a 3-int subset.
Subcase  4.5. There is an element B in the set T∖{A} such that the set B is a 4-int subset.
Without loss of generality, we assume thatA=Δv1vjvj+1 and B=Δv1vtvt+1, where j<t. Let C={v1,vj,vt,vt+1} and D={v1,vj,vj+1,vt+1}. Then the sets C and D are not 6-int subsets. If the set C is an 8-int subset or the set B is an 8-int subset then, by Lemma 6, the set P has a 3-int subset. If the set C is a 7-int subset, then the set Δv1vjvt is a 3-int subset, so the set P has a 3-int subset. If the set D is a 7-int subset, then the set Δv1vj+1vt+1 is a 3-int subset, so the set P has a 3-int subset. If the set C is a 5-int subset, then the set Δvjvj+1vt is a 3-int subset, so the set P has a 3-int subset. If the set D is a 5-int subset, then the set Δvj+1vtvt+1 is a 3-int subset, so the set P has a 3-int subset. Next, we assume that the sets C and D are 4-int subsets. Then Δv1vjvt+1 is a 0-int subset. Then the set {vj,vj+1,vt,vt+1} is an 8-int subset. By Lemma 6, the set P has a 3-int subset.
Case  5. There is an element A in the set T such that the set A is an 8-int subset.
By Lemma5, the set P has a 3-int subset.
Case  6. We have i*(A)≤2 for all A∈T.
If there exist elementsA, B, C, and D in the set T such that the sets A, B, C, and D are 2-int subsets where the sets A, B, C, and D put into anticlockwise positions, then the set A∪B∪C is a 6-int subset. Thus, we obtain that there is an element in the set T such that it is a 1-int subset. It is easy to see that P has a 3-int subset.
Therefore, the setP has a 3-int or 6-int subset. This proof is completed.Figure 8
Verticesv1,v2,…,vm are put into counterclockwise positions.Theorem 8.
One hash(3)=8.Proof.
By Lemmas3 and 4, it follows that 8≤h(3)≤9. By Lemmas 5, 6, and 7, we obtain that h(3)≤8. Hence,   h(3)=8.


## 4. Conclusion and Discussion

In [6], 3 is the smallest positive integer such that any finite point set P of at least 3 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 or 4 points in the set P.In [13], 7 is the smallest positive integer such that any finite point set P of at least 7 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 or 5 points in the set P.In this paper, 8 is the smallest positive integer such that any finite point setP of at least 8 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 or 6 points in the set P.In [14], 7 is the smallest positive integer such that any finite point set P of at least 7 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 or 7 points in the set P.In [15], 8 is the smallest positive integer such that any finite point set P of at least 8 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 or 8 points in the set P. Moreover, 9 is the smallest positive integer such that any finite point set P of at least 9 interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 or k points in the set P, where k≥9.For any positive integerk≥4, we let h*(k) be the smallest integer such that every planar point set P with no three collinear points and with at least h*(k) interior points has a subset Q for which the interior of the convex hull of the set Q contains exactly 3 or k points of the set P.For any positive integerk≥3,
(2)h*(k)=min{s:i(P)≥s⟹∃Q⊆Ps.t.i*(Q)=3ork}.Thus, we have the following formulas:(3)h*(k)=3ifk=4;h*(k)=7ifk=5,7;h*(k)=8ifk=6,8;h*(k)=9ifk≥9.



---

*Source: 328095-2013-12-05.xml*