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


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.

  free PDF view@Springer
other papers about this subject
Last update: August 15, 2017.