Homotopic curve shortening and the affine curve-shortening flow

S. Avvakumov, G. Nivasch, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 12:1-12:15.

Download
OA 2020_LIPIcsSoCG_Avvakumov.pdf 575.90 KB

Conference Paper | Published | English

Scopus indexed
Author
Avvakumov, SerhiiIST Austria; Nivasch, Gabriel
Department
Abstract
We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) 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 curve-shortening 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 self-intersections 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.
Publishing Year
Date Published
2020-06-01
Proceedings Title
36th International Symposium on Computational Geometry
Volume
164
Page
12:1 - 12:15
Conference
SoCG: Symposium on Computational Geometry
Conference Location
Zürich, Switzerland
Conference Date
2020-06-22 – 2020-06-26
ISSN
IST-REx-ID

Cite this

Avvakumov S, Nivasch G. Homotopic curve shortening and the affine curve-shortening flow. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020:12:1-12:15. doi:10.4230/LIPIcs.SoCG.2020.12
Avvakumov, S., & Nivasch, G. (2020). Homotopic curve shortening and the affine curve-shortening flow. In 36th International Symposium on Computational Geometry (Vol. 164, p. 12:1-12:15). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.12
Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” In 36th International Symposium on Computational Geometry, 164:12:1-12:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.12.
S. Avvakumov and G. Nivasch, “Homotopic curve shortening and the affine curve-shortening flow,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164, p. 12:1-12:15.
Avvakumov S, Nivasch G. 2020. Homotopic curve shortening and the affine curve-shortening flow. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry vol. 164. 12:1-12:15.
Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” 36th International Symposium on Computational Geometry, vol. 164, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 12:1-12:15, doi:10.4230/LIPIcs.SoCG.2020.12.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2020-06-23
MD5 Checksum
6872df6549142f709fb6354a1b2f2c06


Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1909.00263

Search this title in

Google Scholar
ISBN Search