Personal tools
You are here: Home CG seminar 2020 How to Peel Self-Intersecting Onions
« November 2019 »
November
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
Log in


Forgot your password?
 

How to Peel Self-Intersecting Onions

Wednesday, December 11th, 2019, 16:10

Checkpoint 480

underline

How to Peel Self-Intersecting Onions

Gabriel Nivasch , Ariel

Abstract:

We define and study a discrete process that generalizes the convex-layer decomposition (a.k.a. "onion 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 taking shortcuts around the obstacles and 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.

Although this experimental connection seems hard to prove, we do prove that HCS satisfies some simple properties analogous to those of ACSF.

Joint work with Sergey Avvakumov (IST Austria).

Links:
https://arxiv.org/abs/1909.00263
https://youtu.be/HaGVe5LnsEg
https://youtu.be/D3mFSAfzuJM
 
Document Actions