Computing optimal homotopies over a spiked plane with polygonal boundary

B. Burton, E.W. Chambers, M.J. Van Kreveld, W. Meulemans, T.A.E. Ophelders, B. Speckmann

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)
87 Downloads (Pure)


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.

Original languageEnglish
Title of host publicationProc. 25th European Symposium on Algorithms (ESA)
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Print)978-3-95977-049-1
Publication statusPublished - 1 Sept 2017
Event25th Annual European Symposium on Algorithms (ESA 2017) - Vienna, Austria
Duration: 4 Sept 20176 Sept 2017
Conference number: 25

Publication series

ISSN (Electronic)1868-8969


Conference25th Annual European Symposium on Algorithms (ESA 2017)
Abbreviated titleESA 2017
Internet address


  • Fréchet distance
  • Geodesic
  • Homotopy
  • Obstacle
  • Polygonal domain


Dive into the research topics of 'Computing optimal homotopies over a spiked plane with polygonal boundary'. Together they form a unique fingerprint.

Cite this