The maximum size of a convex polygon in a restricted set of points in the plane |
| |
Authors: | N Alon M Katchalski W R Pulleyblank |
| |
Institution: | (1) Department of Mathematics, Tel Aviv University, Tel Aviv, Israel;(2) Department of Mathematics, Technion-Israel Institute of Technology, Haifa, Israel;(3) Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada |
| |
Abstract: | Assume we havek points in general position in the plane such that the ratio between the maximum distance of any pair of points to the minimum distance of any pair of points is at most![agr](/content/f367434x62858380/xxlarge945.gif) k, for some positive constant . We show that there exist at least k
1/4 of these points which are the vertices of a convex polygon, for some positive constant = ( ). On the other hand, we show that for every fixed >0, ifk>k( ), then there is a set ofk points in the plane for which the above ratio is at most 4 k, which does not contain a convex polygon of more thank
1/3+
vertices.The work of the first author was supported in part by the Allon Fellowship, by the Bat Sheva de Rothschild Foundation, by the Fund for Basic Research administered by the Israel Academy of Sciences, and by the Center for Absorbtion in Science. Work by the second author was supported by the Technion V. P.R. Fund, Grant No. 100-0679. The third author's work was supported by the Natural Sciences and Engineering Research Council, Canada, and the joint project Combinatorial Optimization of the Natural Science and Engineering Research Council (NSERC), Canada, and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|