Shortest paths for line segments

DOI10.1007/BF01891839MaRDI QIDQ686741zbMATH OpenOpenAlexWikidataFDO

Authors Christian Icking, Günter Rote, Chee K. Yap, Emo Welzl

Publication date 13 October 1993

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01891839

zbMATH Keywords

Cauchy's surface-area formulamotion planningoptimizationUlam's problem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies and applications (68U99)

Review text

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 under the measure \(d_ 2\), the average orbit length of the two endpoints. The problem of \(d_ 2\) optimal motion has been solved by \textit{A. B. Gurevich} [The ``most economical displacement of a segment, Differential Equations 11, 2134-2142 (1975; Zbl 0334.49049)] and also by \textit{V. A. Dubovitskij} [The Ulam problem of optimal motion of line segments, Springer-Verlag, New York (1985; Zbl 0565.49016)], 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.

Recommendations

• Shortest paths of bounded curvature in the plane
• scientific article; zbMATH DE number 1182917
• Shortest paths in the plane with polygonal obstacles
• Shortest polygonal paths in space
• On Shortest Paths in Polyhedral Spaces

Cites work

• A note on the Papadimitriou-Silverberg algorithm for planning optimal piecewise-linear motion of a ladder
• scientific article; zbMATH DE number 3141308 (Why is no real title available?)
• scientific article; zbMATH DE number 3156882 (Why is no real title available?)
• scientific article; zbMATH DE number 3160756 (Why is no real title available?)
• On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
• Optimal piecewise linear motion of an object among obstacles
• The Minimum Path and the Minimum Motion of a Moved Line Segment
• Über Kurven konstanter Breite

Cited in

(14)

• Time-optimal trajectories of a rod in the plane subject to velocity constraints
• Pasting gauges. I: Shortest paths across a hyperplane
• Shortest path geometric rounding
• Watchman routes for lines and line segments
• Shortest curves for vehicles on surfaces of celestial bodies
• Shortest path to a segment and quickest visibility queries
• An approximation algorithm ford₁-optimal motion of a rod robot with fixed rotations
• scientific article; zbMATH DE number 3901519 (Why is no real title available?)
• scientific article; zbMATH DE number 1305420 (Why is no real title available?)
• scientific article; zbMATH DE number 7151640 (Why is no real title available?)
• Is a straight line the shortest path?
• Shortest coordinated motion for square robots
• The Shortest Distance Problem: An Elementary Solution
• A question of Bellman

This page was built for publication: Shortest paths for line segments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686741)