Planar point sets with a small number of empty convex polygons

Abstract

A subset A of a finite set P of points in the plane is called an empty polygon , if each point of A is a vertex of the convex hull of A and the convex hull of A contains no other points of P . We construct a set of n points in general position in the plane with only ˜1.62 n 2 empty triangles, ˜1.94 n 2 empty quadrilaterals, ˜1.02 n 2 empty pentagons, and ˜0.2 n 2 empty hexagons.