Gabriel Nivasch (Ariel University)

Monday, April 30, 2018, 14:10 – 15:10, -101

Abstract:

Experimentally, the convex-layer decomposition of subsets of the integer grid (“grid peeling”) seems to behave at the limit like the affine curve-shortening flow. We offer some theoretical arguments to explain this phenomenon. In particular, we derive some rigorous results for the special case of peeling the quarter-infinite grid: We prove that, in this case, the number of grid points removed up to iteration $n$ is $\Theta(n^{3/2}\log{ n})$ and moreover, the boundary at iteration $n$ is sandwiched between two hyperbolas that are separated from each other by a constant factor. Joint work with David Eppstein and Sariel Har-Peled