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


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