Burton, Benjamin ;
Chambers, Erin ;
van Kreveld, Marc ;
Meulemans, Wouter ;
Ophelders, Tim ;
Speckmann, Bettina
Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary
Abstract
Computing optimal deformations between two curves is a fundamental question with various applications, and has recently received much attention in both computational topology and in mathematics in the form of homotopies of disks and annular regions. In this paper, we examine this problem in a geometric setting, where we consider the boundary of a polygonal domain with spikes, point obstacles that can be crossed at an additive cost. We aim to continuously morph from one part of the boundary to another, necessarily passing over all spikes, such that the most expensive intermediate curve is minimized, where the cost of a curve is its geometric length plus the cost of any spikes it crosses.
We first investigate the general setting where each spike may have a different cost. For the number of inflection points in an intermediate curve, we present a lower bound that is linear in the number of spikes, even if the domain is convex and the two boundaries for which we seek a morph share an endpoint. We describe a 2approximation algorithm for the general case, and an optimal algorithm for the case that the two boundaries for which we seek a morph share both endpoints, thereby representing the entire boundary of the domain.
We then consider the setting where all spikes have the same unit cost and we describe a polynomialtime exact algorithm. The algorithm combines structural properties of homotopies arising from the geometry with methodology for computing Fréchet distances.
BibTeX  Entry
@InProceedings{burton_et_al:LIPIcs:2017:7863,
author = {Benjamin Burton and Erin Chambers and Marc van Kreveld and Wouter Meulemans and Tim Ophelders and Bettina Speckmann},
title = {{Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {23:123:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7863},
URN = {urn:nbn:de:0030drops78630},
doi = {10.4230/LIPIcs.ESA.2017.23},
annote = {Keywords: Fr{\'e}chet distance, polygonal domain, homotopy, geodesic, obstacle}
}
2017
Keywords: 

Fréchet distance, polygonal domain, homotopy, geodesic, obstacle 
Seminar: 

25th Annual European Symposium on Algorithms (ESA 2017)

Issue date: 

2017 
Date of publication: 

2017 