DIMACS TR: 97-66
A Generalization of the Erdos-Szekeres
Theorem to Disjoint Convex Sets
Authors: János Pach and Géza Tóth
ABSTRACT
Let ${\cal F}$ denote a family of pairwise disjoint convex
sets in the plane. ${\cal F}$ is said to be in {\em convex
position}, if none of its members is contained in the convex
hull of the union of the others. For any fixed $k\geq 3$, we
estimate $P_k(n)$, the maximum size of a family ${\cal F}$
with the property that any $k$ members of ${\cal 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\'oth by showing that $P_3(n)<16^n$.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-66.ps.gz
DIMACS Home Page