Stefan Felsner
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin, Germany
email: felsner@inf.fu-berlin.de
Ferran Hurtado
Departament de Matemàtica Aplicada II
Universitat Politècnica de Catalunya
Pau Gargallo 5, E-08028-Barcelona, Spain
Marc Noy
Departament de Mathemàtica Aplicada II
Universitat Politècnica de Catalunya
Pau Gargallo 5, E-08028-Barcelona, Spain
Report B 97-10
November 1997
A k-set of a finite set S of points in the plane is a
subset of cardinality k that can be separated from the rest by
a straight line. The question of how many k-sets a set of
n points can contain is a longstanding open problem where a
lower bound of $\omega(n \log k)$ and an upper bound of 0(nk1/3)
are known today.
Under certain restrictions of the set S, for example, if all
points lie on a convex curve, a linear upper bound can be
shown. Here, we will generalize this observation by showing that if
the points of S lie on a constant number of convex curves, the
number of k-sets remain linear in n.
Get the report here or by anonymous ftp: Server: fubinf.inf.fu-berlin.de File: pub/reports/tr-b-97-10.ps.gz