The Maximum Piercing Number for some Classes of Convex Sets with the $(4,3)$-property

  • Jan Kynčl
  • Martin Tancer

Abstract

A finite collection ${\cal C}$ of closed convex sets in ${\Bbb R}^d$ is said to have a $(p,q)$-property if among any $p$ members of ${\cal C}$ some $q$ have a non-empty intersection, and $|{\cal C}| \ge p$. A piercing number of ${\cal C}$ is defined as the minimal number $k$ such that there exists a $k$-element set which intersects every member of ${\cal C}$. We focus on the simplest non-trivial case in ${\Bbb R}^2$, i.e., $p=4$ and $q=3$. It is known that the maximum possible piercing number of a finite collection of closed convex sets in the plane with $(4,3)$-property is at least $3$ and at most $13$. We consider the following three special types of collections of closed convex sets: segments in ${\Bbb R}^d$, unit discs in the plane and positively homothetic triangles in the plane, in each case only those satisfying $(4,3)$-property. We prove that the maximum possible piercing number is $2$ for the collections of segments and $3$ for the collections of the other two types.

Published
2008-02-04
Article Number
R27