The layer number of evenly distributed point sets

Abstract

For a finite point set X in $\R^d$, we consider a peeling process that in each step removes a convex layer, i.e. the set of vertices of the convex hull. The layer number L(X) of the point set X is defined as the minimum number of steps of the peeling process needed to delete whole set $X$. It is known that the expectation of L(X) is given by $E[L(X)]=\Theta(

X

^{2/(d+1)})$ if X is a set of random points in $R^d$, and recently it was shown that $L(X)=\Theta(

^{2/3})$ if $X$ is a point set of the square grids in the plane.

In this paper, we consider the case of evenly distributed point sets which can be expressed in terms of geometric discrepancy. We find an upper bounds $O(

^{3/4})$ of the layer number of an evenly distributed point set X in a unit disk in the plane and give an explicit construction to show that the upper bound cannot be improved. In addition, we give a generalized upper bound $O(

^{2/d})$ of the layer number of an evenly distributed point set X in a unit ball in $R^d$ for $d\geq 3$.