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

Original language | English |
---|---|

Title of host publication | Proc. 25th European Symposium on Algorithms (ESA) |

Place of Publication | Dagstuhl |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Pages | 1-14 |

ISBN (Print) | 978-3-95977-049-1 |

DOIs | |

Publication status | Published - 1 Sept 2017 |

Event | 25th Annual European Symposium on Algorithms (ESA 2017) - Vienna, Austria Duration: 4 Sept 2017 → 6 Sept 2017 Conference number: 25 https://algo2017.ac.tuwien.ac.at/esa/ |

### Publication series

Name | LIPICS |
---|---|

Volume | 87 |

ISSN (Electronic) | 1868-8969 |

### Conference

Conference | 25th Annual European Symposium on Algorithms (ESA 2017) |
---|---|

Abbreviated title | ESA 2017 |

Country/Territory | Austria |

City | Vienna |

Period | 4/09/17 → 6/09/17 |

Internet address |

## Keywords

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