Personal tools
You are here: Home CG seminar 2020 How to Peel Self-Intersecting Onions
« August 2020 »
Log in

Forgot your password?

How to Peel Self-Intersecting Onions

Wednesday, December 11th, 2019, 16:10

Checkpoint 480


How to Peel Self-Intersecting Onions

Gabriel Nivasch , Ariel


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).

Document Actions