## 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