Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary

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.