Constructions from empty polygons
- PDF / 159,414 Bytes
- 8 Pages / 595 x 842 pts (A4) Page_size
- 93 Downloads / 269 Views
CONSTRUCTIONS FROM EMPTY POLYGONS Tibor Bisztriczky (Calgary), Kiyoshi Hosono (Shimizu), ´rolyi∗ (Budapest) and Masatsugu Urabe∗∗ (Shimizu) Gyula Ka [Communicated by: Imre B´ ar´ any ]
Abstract Let P denote a finite set of points, in general position in the plane. In this note we study conditions which guarantee that P contains the vertex set of a convex polygon that has exactly k points of P in its interior.
1. Introduction In 1935, Erd˝ os and Szekeres [3] proved that for every integer t ≥ 3 there is a smallest number f (t) such that every set P of at least f (t) points, no three collinear, contains a subset of points whose convex hull has precisely t vertices. There is no similar result if the interior of the convex hull of the subset has to be empty. In fact, Horton [4] constructed arbitrarily large point sets P which do not contain 7 vertices of a convex polygon whose interior is disjoint from P . This result has very recently been extended by Nyklov´ a [8], see also [2] for a survey of related problems. Let P be a fixed set of points, in general position in the plane. Assume that C ⊆ P is the vertex set of a convex n-gon. Such a set C will be referred to as n points is convex position, or often, if it is not misleading, simply as a convex n-gon. For any subset S ⊆ P , those points of P that lie in the interior of conv(S) will be called the interior points of S. Here conv(S) stands for the convex hull of S. A convex polygon C ⊆ P is called empty if it has no interior points. Thus, there exist arbitrarily large point sets P that do not contain empty heptagons. The first nontrivial condition which implies that P contains the vertex set of an empty convex n-gon was given in [6]. Mathematics subject classification number: 52C10. Key words and phrases: point configurations, combinatorial convexity, Erd˝ os–Szekeres theorem, empty polygon. * Visiting at the R´ enyi Institute of the Hungarian Academy of Sciences. Research partially supported by Hungarian Scientific Research Grant OTKA T043631. ** Research partially supported by Grant-in-Aid for Scientific Research of the Ministry of Education, Culture, Sports, Science and Technology of Japan, 13640137. 0031-5303/2004/$20.00 c Akad´ emiai Kiad´ o, Budapest
Akad´ emiai Kiad´ o, Budapest Kluwer Academic Publishers, Dordrecht
2
t. bisztriczky et al.
Let K denote a fixed nonnegative integer. If every triple in P determines a triangle with at most K interior points, then P is said to be K-convex. Valtr [9] extended the above mentioned result of K´ arolyi, Pach and T´ oth [6] (which only covered the case K = 1) to the following Theorem A ([9]). For any K ≥ 0 and N ≥ 3, there is a smallest integer f (K, N ) such that every K-convex set of at least f (K, N ) points in general position in the plane determines an empty convex N -gon. N +1
was found by Kun and Lippner An explicit upper bound f (K, N ) ≤ 2(K+2) [7]. See [10] for an even stronger result related to the Erd˝ os–Szekeres problem. In [1], Avis et al. initiated the following problem. Find conditions which guarantee
Data Loading...
