---
res:
bibo_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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sergey
foaf_name: Avvakumov, Sergey
foaf_surname: Avvakumov
foaf_workInfoHomepage: http://www.librecat.org/personId=3827DAC8-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Gabriel
foaf_name: Nivasch, Gabriel
foaf_surname: Nivasch
bibo_doi: 10.4230/LIPIcs.SoCG.2020.12
bibo_volume: 164
dct_date: 2020^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/18688969
- http://id.crossref.org/issn/9783959771436
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Homotopic curve shortening and the affine curve-shortening flow@
...