132
Views
1
CrossRef citations to date
0
Altmetric
Original Articles

Grid Peeling and the Affine Curve-Shortening Flow

, & ORCID Icon
 

ABSTRACT

In this article, 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 GZ2 of the integer grid, previously studied for the particular case G = {1, …, m}2 by Har-Peled and Lidický. The second one is the affine curve-shortening flow (ACSF), first studied by Alvarez et al. and Sapiro and Tannenbaum. 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/2log n); and (2) the boundary at iteration n is sandwiched between two hyperbolas that are separated from each other by a constant factor.

2010 AMS SUBJECT CLASSIFICATION:

Acknowledgements

The third author would like to thank Franck Assous and Elad Horev for useful conversations.

Notes

1 Note that Gn − 1 might contain points which lie on the boundary of Hn but are not vertices. These points will still be present in Gn.

2 This seems to be the case empirically.

3 Actually, for R5 we did not simulate ACSF. We simply used the closed-form solution given by r(t) = (r(0)4/3 − 4t/3)3/4, where r(t) is the radius of the circle at time t.

4 We computed the Hausdorff distances using a simple brute-force approach, using the fact that for convex polygonal chains the maximum distance is attained by a vertex (Atallah [CitationAtallah 83]). (Atallah [CitationAtallah 83] also presented a more efficent Hausdorff-distance algorithm for convex polygonal chains, which we did not use.)

5 The techniques of [CitationHar-Peled and Lidický 13] are also presented in Section 5 below.

6 The existence of a unique solution was proven for doubly-differentiable curves, without the assumption of closedness, by Angenent et al. [CitationAngenent et al. 98, Section 6] and stated for closed curves without the assumption of smoothness in [CitationCao 03, Theorem 3.28]. In the case here, the uniqueness of the solution can be proven by applying the result for closed curves to the boundary of a large square: if the quarterplane had multiple solutions, they could be approximated arbitrarily well by the solution near the corner of a large enough square, which would necessarily also have multiple solutions, violating [CitationCao 03, Theorem 3.28].

Additional information

Funding

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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.