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