## Rainer E. Burkard, Günter Rote, En-Yu Yao, and Zhong-Liang Yu:

# Shortest polygonal paths in space

*Computing* **45** (1990), 51–68, (Zbl. 722.68098,
MR #91g:68157).
doi:10.1007/BF02250584*
*
### Abstract

For a polygonal path in the plane or in space, we want to find an
inscribed path of shortest circumference. In the *open* case the path
can have different start and end point, whereas in the *closed* case
these two points must coincide. We show that finding such shortest paths can
be reduced to finding a shortest path in a planar *channel*. This
problem can be solved in linear time in the open as well in the closed
case. Finally, we deal with constrained problems where the wanted path has to
fulfill additional properties; in particular, if it has to pass straight
through a further point, we show that the length of such a constrained
polygonal path is a strictly convex function of some parameter angle, and
we derive an algorithm for determining such constrained polygonal paths
efficiently.

Last update: August 15, 2017.