SHORTEST PATHS FOR LINE SEGMENTS

Citation
C. Icking et al., SHORTEST PATHS FOR LINE SEGMENTS, Algorithmica, 10(2-4), 1993, pp. 182-200
Citations number
16
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Applications & Cybernetics
Journal title
ISSN journal
01784617
Volume
10
Issue
2-4
Year of publication
1993
Pages
182 - 200
Database
ISI
SICI code
0178-4617(1993)10:2-4<182:SPFLS>2.0.ZU;2-L
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 averag e 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 o f obstacles). We characterize all shortest paths of the line segment m oving in free space under the measure d2, the average orbit length of the two endpoints. The problem of d2 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.