David Eppstein,
Gabriel Nivasch, and
Sariel Har-Peled.
In this paper we study an experimentally-observed connection
between two seemingly unrelated processes, one from computational
geometry and the other from differential geometry. The first one
(which we call (grid peeling) is the convex-layer
decomposition of subsets $G\subset \Z^2$ of the integer grid,
previously studied for the particular case $G=\{1,\ldots,m\}^2$ by
Har-Peled and Lidicky. The second one
is the affine curve-shortening flow (ACSF), first studied by
Alvarez etal (1993) and Sapiro and Tannenbaum (1993). We present
empirical evidence that, in a certain well-defined sense, grid
peeling behaves at the limit like ACSF on convex curves. We offer
some theoretical arguments in favor of this conjecture.
We also pay closer attention to the simple case where $G=\N^2$ is a
quarter-infinite grid. This case corresponds to ACSF starting with
an infinite L-shaped curve, which when transformed using the ACSF
becomes a hyperbola for all times $t>0$. We prove that, in the grid
peeling of $\N^2$, (1) the number of grid points removed up to
iteration $n$ is $\Theta(n^{3/2}\log n)$; and (2) the boundary at
iteration $n$ is sandwiched between two hyperbolas that are
separated from each other by a constant factor.
PDF.
Last modified: Wed 2018-05-30 21:07:14 UTC 2018 by Sariel Har-Peled