## Christian Icking, Günter Rote, Emo Welzl, and Chee Yap:

# Shortest paths for line segments

*Algorithmica* **10** (1993), 182–200. (Zbl 781.68118). doi:10.1007/BF01891839*
*
### Abstract

We study the problem of shortest paths for a line segment in the plane. As
a measure of the distance traversed by a path, we take the average curve
length of the orbits of prescribed points on the line segment. This problem
is nontrivial even in free space (i. e., in the absence of obstacles).
We characterize all shortest paths of the line segment moving in free space
when we measure the average orbit length of the two endpoints.

This problem of optimal motion has been solved by Gurevich and also by
Dubovitskij, who calls it Ulam's problem. Unlike previous solutions, our basic
tool is Cauchy's surface-area formula. This new approach is relatively
elementary, and yields new insights.

Last update: August 15, 2017.