DIMACS TR: 97-66

A Generalization of the Erdos-Szekeres Theorem to Disjoint Convex Sets

Authors: János Pach and Géza Tóth


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