Peeling the Grid

Abstract

Consider the set of points formed by the integer $n\times 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\times n$ grid is Θ(n^{4/3}).

8 pages, 4 figures

Cited by in corpus (2)

• Grid peeling and the affine curve-shortening flow
• New estimates for convex layer numbers