# Point-sets with few k-sets

### Helmut Alt Institut für Informatik Freie Universität Berlin Takustr. 9. D-14195 Berlin, Germany email: alt@inf.fu-berlin.de 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