Shortest paths for line segments

Christian Icking, Günter Rote, Emo Welzl, Chee Yap

Research output: Contribution to journalArticlepeer-review

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 under the measure d 2, the average orbit length of the two endpoints. The problem of d 2 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.

Original languageEnglish (US)
Pages (from-to)182-200
Number of pages19
JournalAlgorithmica
Volume10
Issue number2-4
DOIs
StatePublished - Oct 1993

Keywords

  • Cauchy's surface-area formula
  • Motion planning
  • Optimal motion
  • Ulam's problem

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Shortest paths for line segments'. Together they form a unique fingerprint.

Cite this