DIMACS TR: 98-26
Erdös-Szekeres-Type Theorems for Segments and Non-crossing Convex Sets
Authors: János Pach and Géza Tóth
ABSTRACT
A family $\cal F$ of convex sets is said to be in convex
position, if none of its members is contained in the convex
hull of the others. It is proved that there is a function $N(n)$
with the following property. If $\cal F$ is a family of at least
$N(n)$ plane convex sets with non-empty interiors, such that any two
members
of $\cal F$ have at most two boundary points in common and any three
are in convex position, then $\cal F$ has $n$ members in convex
position. This result generalizes a theorem of T. Bisztriczky and
G. Fejes Tóth \cite{BF1}. The statement does not remain true,
if two members of $\cal F$ may share four boundary points.
This follows from the fact that there exist
infinitely many straight-line segments
such that any three are in convex position, but no four are.
However, there is a function $M(n)$ such that every family of
at least $M(n)$ segments, any four of which are in convex
position, has $n$ members in convex position.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-26.ps.gz
DIMACS Home Page