Grid peeling and the affine curve-shortening flow

David Eppstein, Sariel Har-Peled, Gabriel Nivasch

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
EditorsRasmus Pagh, Suresh Venkatasubramanian
PublisherSociety for Industrial and Applied Mathematics Publications
Pages109-116
Number of pages8
ISBN (Electronic)9781611975055
DOIs
StatePublished - 2018
Event20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 8 2018

Publication series

NameProceedings of the Workshop on Algorithm Engineering and Experiments
Volume2018-January
ISSN (Print)2164-0300

Other

Other20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
CountryUnited States
CityNew Orleans
Period1/7/181/8/18

ASJC Scopus subject areas

  • Engineering(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Grid peeling and the affine curve-shortening flow'. Together they form a unique fingerprint.

Cite this