A Generalization of the Erdos - Szekeres Theorem to Disjoint Convex Sets |
| |
Authors: | J Pach G Tóth |
| |
Institution: | (1) Courant Institute, NYU, 251 Mercer Street, New York, NY 10012, USA and Mathematical Institute, Hungarian Academy of Sciences, Pf 127, H-1364 Budapest, Hungary \{pach,geza\}@math-inst.hu, US |
| |
Abstract: | Let F denote a family of pairwise disjoint convex sets in the plane. F is said to be in convex position if none of its members is contained in the convex hull of the union of the others. For any fixed k≥ 3 , we estimate P
k
(n) , the maximum size of a family F with the property that any k members of F are in convex position, but no n are. In particular, for k=3 , we improve the triply exponential upper bound of T. Bisztriczky and G. Fejes Tóth by showing that P
3
(n) < 16
n
.
<lsiheader>
<onlinepub>26 June, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>19n3p437.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received March 27, 1997, and in revised form July 10, 1997. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|