The Study Of Erdos-szekeres Problem About Finite Point Sets

In1978Erdos posed the empty polygon version of the original Erdos-Szekeres prob-lem. For any positives integer n≥3, determine the smallest integer H(n),if it exists, such that any set X of at least H(n) points in general position in the plane contains n points which are the vertices of an empty convex polygon. Generalizing the Erdos prob-lem on empty convex polygons, Bisztriczky and Soltan defined Hd(n)(d≥2and n≥1) to be the smallest positive integer, if it exixts, such that any set X of Hd(n) points in general positive in Ed contains a subset of n points that are the vertices of an empty convex polytope. In this paper, we consider a generalization of the problem above:1. Denote by Gd(n)(d≥2and n≥1) the smallest positive integer (if it exists) such that any set X of Gd(n) points, at most d+1points in a hyperplane of Ed, contains a subset of n points that are the vertices of an empty convex polytope, and prove that G2(3)=4, G2(4)=7,G2(5)≥16, G3(4)=5, and G3(5)=9.2.For a planar finite point set S, at most3points in a hyperplane of E3are allowed, How many disjoint empty convex k-gons can be constructed in the point set S for a fixed k? We mainly study k=4. Moreover, we consider the minimum number number of disjoint empty convex polygons for a given point set.