Grid peeling and the affine curve-shortening flow

Seminar
Speaker
Gabriel Nivasch (Ariel University)
Date
28/10/2018 - 15:30 - 14:00Add to Calendar 2018-10-28 14:00:00 2018-10-28 15:30:00 Grid peeling and the affine curve-shortening flow 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. Room 201, Math and CS Building (Bldg. 216) אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 201, Math and CS Building (Bldg. 216)
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.

Last Updated Date : 21/10/2018