The study of k- sets is a very relevant topic in the research area of computational geometry. The study of the maximum and minimum number of k-sets in sets of points of the plane in general position, specifically, has...The study of k- sets is a very relevant topic in the research area of computational geometry. The study of the maximum and minimum number of k-sets in sets of points of the plane in general position, specifically, has been developed at great length in the literature. With respect to the maximum number of k-sets, lower bounds for this maximum have been provided by Erdaos et al., Edelsbrunner and Welzl, and later by Toth. Dey also stated an upper bound for this maximum number of k-sets. With respect to the minimum number of k-set, this has been stated by Erdos el al. and, independently, by Lovasz et al. In this paper the authors give an example of a set ofn points in the plane in general position （no three collinear）, in which the minimum number of points that can take part in, at least, a k-set is attained for every k with 1 ≤ k 〈 n/2. The authors also extend Erdos＇s result about the minimum number of points in general position which can take part in a k-set to a set ofn points not necessarily in general position. That is why this work complements the classic works we have mentioned before.展开更多
文摘The study of k- sets is a very relevant topic in the research area of computational geometry. The study of the maximum and minimum number of k-sets in sets of points of the plane in general position, specifically, has been developed at great length in the literature. With respect to the maximum number of k-sets, lower bounds for this maximum have been provided by Erdaos et al., Edelsbrunner and Welzl, and later by Toth. Dey also stated an upper bound for this maximum number of k-sets. With respect to the minimum number of k-set, this has been stated by Erdos el al. and, independently, by Lovasz et al. In this paper the authors give an example of a set ofn points in the plane in general position （no three collinear）, in which the minimum number of points that can take part in, at least, a k-set is attained for every k with 1 ≤ k 〈 n/2. The authors also extend Erdos＇s result about the minimum number of points in general position which can take part in a k-set to a set ofn points not necessarily in general position. That is why this work complements the classic works we have mentioned before.
