Consider the set of points formed by the integer n x n grid,
and the process that in each iteration removes from the point set the
vertices of its convex-hull. Here, we prove that the number of
iterations of this process is O(n^{4/3}); that is, the
number of convex layers of the n x n grid is
Theta(n^{4/3}).
PDF.
Last modified: Mon Jul 2 16:02:03 CDT 2012