d1-optimal motion for a rod

Tetsuo Asano; David Kirkpatrick; Chee K. Yap

d₁-optimal motion for a rod

Tetsuo Asano, David Kirkpatrick, Chee K. Yap

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

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 d₁-optimal motion, and an efficient approximation algorithm.

Original language	English (US)
Pages	252-263
Number of pages	12
State	Published - 1996
Event	Proceedings of the 1996 12th Annual Symposium on Computational Geometry - Philadelphia, PA, USA Duration: May 24 1996 → May 26 1996

Other

Other	Proceedings of the 1996 12th Annual Symposium on Computational Geometry
City	Philadelphia, PA, USA
Period	5/24/96 → 5/26/96

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Cite this

@conference{7ae445b2917549caabfe4bc75a64a095,

title = "d1-optimal motion for a rod",

abstract = "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.",

author = "Tetsuo Asano and David Kirkpatrick and Yap, {Chee K.}",

year = "1996",

language = "English (US)",

pages = "252--263",

note = "Proceedings of the 1996 12th Annual Symposium on Computational Geometry ; Conference date: 24-05-1996 Through 26-05-1996",

}

TY - CONF

T1 - d1-optimal motion for a rod

AU - Asano, Tetsuo

AU - Kirkpatrick, David

AU - Yap, Chee K.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0029703026&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029703026&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0029703026

SP - 252

EP - 263

T2 - Proceedings of the 1996 12th Annual Symposium on Computational Geometry

Y2 - 24 May 1996 through 26 May 1996

ER -

d₁-optimal motion for a rod

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this