d1-optimal motion for a rod

Tetsuo Asano, David Kirkpatrick, Chee K. Yap

Research output: Contribution to conferencePaperpeer-review


We study the motion of a rod (line segment) in the plane in the presence of polygonal obstacles, under an optimality criterion based on minimizing the orbit length of a fixed but arbitrary point (called the focus) on the rod. Our central result is that this problem is NP-hard when the focus is in the relative interior of the rod. Other results include a local characterization of this so-called d1-optimal motion, and an efficient approximation algorithm.

Original languageEnglish (US)
Number of pages12
StatePublished - 1996
EventProceedings of the 1996 12th Annual Symposium on Computational Geometry - Philadelphia, PA, USA
Duration: May 24 1996May 26 1996


OtherProceedings of the 1996 12th Annual Symposium on Computational Geometry
CityPhiladelphia, PA, USA

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'd1-optimal motion for a rod'. Together they form a unique fingerprint.

Cite this