Convex independent sets and 7-holes in restricted planar point sets |
| |
Authors: | Pavel Valtr |
| |
Institution: | (1) Department of Applied Mathematics, Charles University, Malostranské nám. 25, 11800 Praha 1, Czechoslovakia;(2) Institut für Informatik, Freie Universität Berlin, Arnimallee 2-6, 1000 Berlin 33, Federal Republic of Germany |
| |
Abstract: | For a finite setA of points in the plane, letq(A) denote the ratio of the maximum distance of any pair of points ofA to the minimum distance of any pair of points ofA. Fork>0 letc
(k) denote the largest integerc such that any setA ofk points in general position in the plane, satisfying
for fixed
, contains at leastc convex independent points. We determine the exact asymptotic behavior ofc
(k), proving that there are two positive constants=(), such thatk
1/3c
(k)k
1/3. To establish the upper bound ofc
(k) we construct a set, which also solves (affirmatively) the problem of Alonet al. 1] about the existence of a setA ofk points in general position without a 7-hole (i.e., vertices of a convex 7-gon containing no other points fromA), satisfying
. The construction uses Horton sets, which generalize sets without 7-holes constructed by Horton and which have some interesting properties. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|