TY - GEN

T1 - Grid peeling and the affine curve-shortening flow

AU - Eppstein, David

AU - Har-Peled, Sariel

AU - Nivasch, Gabriel

N1 - Funding Information:
Supported in part by the National Science Foundation under Grants CCF-1228639, CCF-1618301, and CCF-1616248. Work on this paper was partially supported by a NSF AF awards CCF-1421231 and CCF-1217462.
Publisher Copyright:
Copyright © 2018 by SIAM.

PY - 2018

Y1 - 2018

N2 - 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 ? Z2 of the integer grid, previously studied for the particular case G = {1, . . ., m}2 by Har-Peled and Lidický (2013). The second one is the affine curve-shortening flow (ACSF), first studied by Alvarez et al. (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 = N2 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 N2, (1) the number of grid points removed up to iteration n is ?(n3/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.

AB - 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 ? Z2 of the integer grid, previously studied for the particular case G = {1, . . ., m}2 by Har-Peled and Lidický (2013). The second one is the affine curve-shortening flow (ACSF), first studied by Alvarez et al. (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 = N2 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 N2, (1) the number of grid points removed up to iteration n is ?(n3/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.

UR - http://www.scopus.com/inward/record.url?scp=85041428663&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041428663&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975055.10

DO - 10.1137/1.9781611975055.10

M3 - Conference contribution

AN - SCOPUS:85041428663

T3 - Proceedings of the Workshop on Algorithm Engineering and Experiments

SP - 109

EP - 116

BT - 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018

A2 - Pagh, Rasmus

A2 - Venkatasubramanian, Suresh

PB - Society for Industrial and Applied Mathematics Publications

T2 - 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018

Y2 - 7 January 2018 through 8 January 2018

ER -