<p><strong>This is morally equivalent to a slower variant of the Hershberger-Snoeyink funnel algorithm.</strong></p>

<p>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, <em>Networks</em> 1984; Leiserson and Maley, STOC 1985].</p>

<p>Both your algorithm and the Hershberger-Snoeyink algorithm are examples of a folklore technique called <em>curve shortening</em>.  At a high level: <strong>If the curve can be shortened by a continuous motion, shorten the curve by a continuous motion.</strong>  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 <em>any</em> 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 <em>necessarily</em> converges to the unique shortest path homotopic to the given path.</p>

<p>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.)</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Graham_scan" rel="nofollow noreferrer">Graham scan convex hull algorithm</a>, or <a href="https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain" rel="nofollow noreferrer">Andrews' equivalent sort-and-repair algorithm</a>, or the equivalent plane-sweep algorithm.</p>

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

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

<hr>

<p>One advantage of the Hershberger-Snoeyink algorithm is that it has a single <span class="math-container">$O(n\log n)$</span>-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 <span class="math-container">$O(n\log n + kn)$</span>, where <span class="math-container">$k$</span> is the complexity of the input path.  The analysis is straightforward.</p>

<p>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 <span class="math-container">$O(n \log n)$</span> time, and the number of vertex releases could be as high as <span class="math-container">$\Omega(kn)$</span>.  Suppose we want to simplify the black path in the following example:</p>

<p><a href="https://i.sstatic.net/3o1HP.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/3o1HP.png" alt="A path and a polygon with lots of vertex releases"></a></p>

<p>For simplicity, suppose we repeatedly release the first unstable vertex on the black path.  The first release creates <span class="math-container">$\Omega(n)$</span> new path vertices; the next <span class="math-container">$\Omega(n)$</span> 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.)</p>

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

<p>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 <span class="math-container">$o(n^{4/3})$</span> time.  See [<a href="https://doi.org/10.1145/513400.513421" rel="nofollow noreferrer">Cabello et al. 2004</a>] and [<a href="https://doi.org/10.1016/S0196-6774(03)00090-7" rel="nofollow noreferrer">Bespanyatnikh 2003</a>] for similar hardness results and matching theoretical improvements to Hershberger-Snoeyink.</p>

<hr>

<p>tl;dr: I would cite "folklore", at least for correctness.</p>

CC BY-SA 4.0
2019-05-07T19:06:44.447Z
Thanks! BTW I'm not sure what Gromov's uniqueness proof is, but here is a simple proof for the Euclidean plane: Suppose for a contradiction there are two shortest curves D1, D2. We already know they have the same crossing sequence in the triangulation. Let D_mid be the curve obtained by taking the middle point between D1, D2 at each triangulation edge. Then |D_mid| <= (|D_1|+|D_2|)/2, because that's what happens inside each triangle. Furthermore, equality is achieved if and only if D1, D2 are parallel in that triangle. So equality is only achieved if both curves go in a straight line forever.
Gabriel Nivasch
CC BY-SA 4.0
2019-05-13T15:53:02.383Z
I think the vertex release algorithm can also be made to run in time O(n log n + k n): In order to compute convex hulls with Graham's algorithm, you need to sort the points by x only once. After that, the running time is linear. Am I missing something?
Gabriel Nivasch
CC BY-SA 4.0
2019-05-13T19:53:28.113Z
Hmmm. I think this can be made to work, but I strongly suspect the resulting algorithm is still slower in practice. At each step, you need to extract the subset of points inside each unstable triangle _in sorted order_ to compute its convex hull.  This is easy to do in O(n) time with a global scan through the global sorted list; however, the funnel algorithm is faster when the crossing sequence is short, and the global-scan-every-step algorithm isn't.
Jeffε
CC BY-SA 4.0
2019-05-14T07:58:41.967Z
Hi Jeff, we both got confused. The number of vertex releases could be larger than k. It could be as high as k n. Could it be even higher?
Gabriel Nivasch
CC BY-SA 4.0
2019-05-14T10:40:01.840Z
Ah, yes, you're right!  Now that you mention it, an example with Ω(kn) releases is not hard to construct, but I don't see how to get more.  On the other hand, assuming O(kn) is an upper bound on the number of releases, a running time of O(kn log n) or even O(n log n + kn) might still be achievable with the right data structures.  (In the lower bound examples I have in mind, most of the releases are trivial.)
Jeffε
CC BY-SA 4.0
2019-05-07T13:29:07.543Z
2019-05-14T12:14:14.887Z
2019-05-14T12:14:14.887Z
Jeffε
<p>Let <span class="math-container">$C$</span> 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 <span class="math-container">$C$</span>. (A path <span class="math-container">$D$</span> is homotopic to <span class="math-container">$C$</span> if it has the same endpoints as <span class="math-container">$C$</span> and can be obtained from <span class="math-container">$C$</span> 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.)</p>

<p>Here is a simple algorithm for finding <span class="math-container">$D$</span>. Is there any reference to it in the literature?</p>

<p>Call a path vertex <span class="math-container">$v$</span> "unstable" if it does not touch any obstacle, or if it touches an obstacle but the obstacle lies on the side of <span class="math-container">$v$</span> at which the angle is larger than 180 degrees.</p>

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

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

<p>This works also for self-intersecting paths or curves with no problem. </p>

<p>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.</p>

<p>Is there any mention in the literature of this simple algorithm?</p>

<p>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: <a href="http://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/shortest-homotopic-paths.pdf" rel="nofollow noreferrer">http://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/shortest-homotopic-paths.pdf</a></p>

<p><strong>[Added:</strong> For the record, this algorithm was found in joint work with Sergey Avvakumov.<strong>]</strong></p>

<p><a href="https://i.sstatic.net/SBaGr.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/SBaGr.png" alt="Picture"></a></p>

<reference-request><cg.comp-geom><computational-geometry><topology>
Reference request: Shortest homotopic curve via vertex releases
Gabriel Nivasch
# Reference request: Shortest homotopic curve via vertex releases

(Asked by: username_0 on 2019-05-06)

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.**]**

[![Picture](https://i.sstatic.net/SBaGr.png)](https://i.sstatic.net/SBaGr.png)

**Tags:** reference-request, cg.comp-geom, computational-geometry, topology

---

## 1 answers

### Answer by username_1 on 2019-05-07. Score: 6

**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](https://en.wikipedia.org/wiki/Graham_scan), or [Andrews' equivalent sort-and-repair algorithm](https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain), 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:

[![A path and a polygon with lots of vertex releases](https://i.sstatic.net/3o1HP.png)](https://i.sstatic.net/3o1HP.png)

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](https://doi.org/10.1145/513400.513421)] and [[Bespanyatnikh 2003](https://doi.org/10.1016/S0196-6774(03)00090-7)] for similar hardness results and matching theoretical improvements to Hershberger-Snoeyink.

---

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

> **Comments:**
> **username_0**: Thanks! BTW I'm not sure what Gromov's uniqueness proof is, but here is a simple proof for the Euclidean plane: Suppose for a contradiction there are two shortest curves D1, D2. We already know they have the same crossing sequence in the triangulation. Let D_mid be the curve obtained by taking the middle point between D1, D2 at each triangulation edge. Then |D_mid| <= (|D_1|+|D_2|)/2, because that's what happens inside each triangle. Furthermore, equality is achieved if and only if D1, D2 are parallel in that triangle. So equality is only achieved if both curves go in a straight line forever.  
> **username_0**: I think the vertex release algorithm can also be made to run in time O(n log n + k n): In order to compute convex hulls with Graham's algorithm, you need to sort the points by x only once. After that, the running time is linear. Am I missing something?  
> **username_1**: Hmmm. I think this can be made to work, but I strongly suspect the resulting algorithm is still slower in practice. At each step, you need to extract the subset of points inside each unstable triangle _in sorted order_ to compute its convex hull.  This is easy to do in O(n) time with a global scan through the global sorted list; however, the funnel algorithm is faster when the crossing sequence is short, and the global-scan-every-step algorithm isn't.  
> **username_0**: Hi Jeff, we both got confused. The number of vertex releases could be larger than k. It could be as high as k n. Could it be even higher?  
> **username_1**: Ah, yes, you're right!  Now that you mention it, an example with Ω(kn) releases is not hard to construct, but I don't see how to get more.  On the other hand, assuming O(kn) is an upper bound on the number of releases, a running time of O(kn log n) or even O(n log n + kn) might still be achievable with the right data structures.  (In the lower bound examples I have in mind, most of the releases are trivial.)  

---

