## 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_{1}-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

## Fingerprint

Dive into the research topics of 'd_{1}-optimal motion for a rod'. Together they form a unique fingerprint.