License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.23
URN: urn:nbn:de:0030-drops-78630
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7863/
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 2-approximation 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 polynomial-time 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:1--23:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-049-1},
ISSN = {1868-8969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7863},
URN = {urn:nbn:de:0030-drops-78630},
doi = {10.4230/LIPIcs.ESA.2017.23},
annote = {Keywords: Fr{\'e}chet distance, polygonal domain, homotopy, geodesic, obstacle}
}
|
Keywords: |
|
Fréchet distance, polygonal domain, homotopy, geodesic, obstacle |
|
Collection: |
|
25th Annual European Symposium on Algorithms (ESA 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.09.2017 |
