98-27: Finding Convex Sets in Convex Position

DIMACS TR: 98-27

Finding Convex Sets in Convex Position

Author: 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 5$, we give a linear upper bound on $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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-27.ps.gz

DIMACS Home Page