Reference request: Shortest homotopic curve via vertex releases

Question

Let $C$ be a piecewise-linear path (or closed curve) in the plane, in the presence of polygonal obstacles. We would like to find the shortest path (or curve) homotopic to $C$. (A path $D$ is homotopic to $C$ if it has the same endpoints as $C$ and can be obtained from $C$ by modifying it continuously, without crossing any obstacle and without moving the endpoints. For curves the definition is the same except that there is no endpoint requirement.)

Here is a simple algorithm for finding $D$. Is there any reference to it in the literature?

Call a path vertex $v$ "unstable" if it does not touch any obstacle, or if it touches an obstacle but the obstacle lies on the side of $v$ at which the angle is larger than 180 degrees.

An unstable vertex can be "released" resulting in a shorter path, as follows: Let $v$ be an unstable vertex, and let $u$, $w$ be the previous and next vertices of $C$. Let $\Delta$ be the triangle $uvw$, and let $S$ be the set of obstacle vertices contained in $\Delta$. Let $u, z_1, \ldots, z_k, w$ be the sequence of vertices of the convex hull of $S\setminus\{v\}$ in order. Then we replace $v$ by $z_1, \ldots, z_k$. The new vertices $z_i$ will necessarily be stable, but $u$ and $w$ might change from stable to unstable or vice versa.

So then the algorithm is: As long as there is an unstable vertex, pick an arbitrary unstable vertex and release it.

This works also for self-intersecting paths or curves with no problem.

If we allow point obstacles, then we also need to keep information of the "wrap" angle of the curve around each obstacle point. Then the curve is unstable if and only if the wrap angle is between -180 and 180 degrees.

Is there any mention in the literature of this simple algorithm?

The standard approach (which might be more efficient, though perhaps more cumbersome) uses a "funnel", and involves triangulating the empty space. See for example these course notes by Jeff Erickson: http://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/shortest-homotopic-paths.pdf

[Added: For the record, this algorithm was found in joint work with Sergey Avvakumov.]

Answer 1

This is morally equivalent to a slower variant of the Hershberger-Snoeyink funnel algorithm.

I'm not aware of any exposition of your simple algorithm in the literature. This is actually a little surprising, given how many times the basic funnel algorithm has been rediscovered [Tompa, STOC 1980; Chazelle, FOCS 1982; Lee and Preparata, Networks 1984; Leiserson and Maley, STOC 1985].

Both your algorithm and the Hershberger-Snoeyink algorithm are examples of a folklore technique called curve shortening. At a high level: If the curve can be shortened by a continuous motion, shorten the curve by a continuous motion. The details are surprisingly irrelevant; you can shorten either by local discrete moves (like your algorithm) or by a global continuous deformation (as if the path were made of elastic). In any space where curvature is nowhere positive, there is a unique shortest path in every homotopy class [Gromov]. Thus, assuming your shortening process actually converges, it necessarily converges to the unique shortest path homotopic to the given path.

This is exactly why the Hershberger-Snoeyink funnel algorithm works. Each step in reducing the crossing sequence is shortening a subpath of the path to a line segment, and each step in the funnel algorithm is equivalent to shortening the path inside the next triangle of the sleeve. (See my notes linked by OP for definitions.)

In particular, the sides of the funnel play exactly the same role as your convex hulls. Moreover, the standard algorithm for extending the funnel through one triangle is identical to one iteration of the Graham scan convex hull algorithm, or Andrews' equivalent sort-and-repair algorithm, or the equivalent plane-sweep algorithm.

So while I agree that your algorithm is more elementary than Hershberger-Snoeyink, I'm not convinced that it's actually easier to implement.

(One thing that may not be clear in my notes is that the Hershberger-Snoeyink algorithm doesn't actually need to construct the sleeve; the funnel can be guided directly by the reduced crossing sequence. The only point of the sleeve is to help visualize the algorithm.)

---

One advantage of the Hershberger-Snoeyink algorithm is that it has a single $O(n\log n)$-time preprocessing phase to compute a global triangulation, after which the running time is proportional the number of crossings, so the overall worst-case running time is $O(n\log n + kn)$, where $k$ is the complexity of the input path. The analysis is straightforward.

I strongly suspect that the vertex-release algorithm can be polished to have the same running time, with the right combination of preprocessing, data structures, and choice of which unstable vertex to release at each iteration, but it's certainly not straightforward. Naively, your algorithm needs to compute the convex hull of a subset of the points for each vertex release, which takes $O(n \log n)$ time, and the number of vertex releases could be as high as $\Omega(kn)$. Suppose we want to simplify the black path in the following example:

For simplicity, suppose we repeatedly release the first unstable vertex on the black path. The first release creates $\Omega(n)$ new path vertices; the next $\Omega(n)$ releases delete those vertices; and these releases remove one "tooth" from the black path. (Yes, you can reduce the number of releases by choosing them more intelligently, but that complicates the algorithm.)

So assuming this $\Omega(kn)$ lower bound is tight, a naive implementation of this algorithm runs in $O(kn^2\log n)$ time. You can remove a $O(\log n)$ factor by pre-sorting the points; then each step can be performed in $O(n)$ time via Graham's scan.

You might try speeding up the algorithm by releasing the vertex that makes "the most progress", but this is uncomfortably close to 2d simplex range searching, so this "improvement" could easily make the algorithm slower, not faster. For example, deciding whether there is a "trivial" vertex release, which decreases the complexity of the path, is at least as hard as Hopcroft's point-line incidence problem, and therefore is unlikely to be solvable in $o(n^{4/3})$ time. See [Cabello et al. 2004] and [Bespanyatnikh 2003] for similar hardness results and matching theoretical improvements to Hershberger-Snoeyink.

---

tl;dr: I would cite "folklore", at least for correctness.