On the minimum number of empty polygons in planar point sets


Pavel Valtr
Institut für Informatik
Freie Universität Berlin
Report B 92-01
January 1992

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-92-01.ps.gz

We describe a configuration (related to Horton's constructions) of n points in general position in the plane with less than $1.8 n^2$ empty triangles, less than $2.42 n^2$ empty quadrilaterals, less than $1.46 n^2$ empty pentagons, and less than n 2/3 empty hexagons. It improves the constants shown by Bárány and Füredi.

On the minimum number of empty polygons in planar point sets

Pavel Valtr Institut für Informatik Freie Universität Berlin Report B 92-01 January 1992