Avvakumov, Sergey ;
Nivasch, Gabriel
Homotopic Curve Shortening and the Affine CurveShortening Flow
Abstract
We define and study a discrete process that generalizes the convexlayer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might selfintersect) in the presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent.
We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curveshortening flow (ACSF). This connection between HCS and ACSF generalizes the link between "grid peeling" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids.
We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of selfintersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase.
BibTeX  Entry
@InProceedings{avvakumov_et_al:LIPIcs:2020:12170,
author = {Sergey Avvakumov and Gabriel Nivasch},
title = {{Homotopic Curve Shortening and the Affine CurveShortening Flow}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {12:112:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771436},
ISSN = {18688969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12170},
URN = {urn:nbn:de:0030drops121708},
doi = {10.4230/LIPIcs.SoCG.2020.12},
annote = {Keywords: affine curveshortening flow, shortest homotopic path, integer grid, convexlayer decomposition}
}
08.06.2020
Keywords: 

affine curveshortening flow, shortest homotopic path, integer grid, convexlayer decomposition 
Seminar: 

36th International Symposium on Computational Geometry (SoCG 2020)

Issue date: 

2020 
Date of publication: 

08.06.2020 
Supplementary Material: 

Our code is available at https://github.com/savvakumov/. 