English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Approximation of Curvature-constrained Shortest Paths through a Sequence of Points

Lee, J.-H., Cheong, O., Kwon, W.-C., Shin, S.-Y., & Chwa, K.-Y. (2000). Approximation of Curvature-constrained Shortest Paths through a Sequence of Points. In M. Paterson (Ed.), Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00) (pp. 314-325). Berlin, Germany: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3382-5 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3384-1
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Lee, Jae-Ha1, Author           
Cheong, Otfried, Author
Kwon, Woo-Cheol, Author
Shin, Sung-Yong, Author
Chwa, Kyung-Yong, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: Let $B$ be a point robot moving in the plane, whose path is constrained to forward motions with curvature at most 1, and let $\X$ denote a sequence of $n$ points. Let $s$ be the length of the shortest curvature-constrained path for $B$ that visits the points of $\X$ in the given order. We show that if the points of $\X$ are given \emph{on-line} and the robot has to respond to each point immediately, there is no strategy that guarantees a path whose length is at most~$f(n)s$, for any finite function~$f(n)$. On the other hand, if all points are given at once, a path with length at most $5.03 s$ can be computed in linear time. In the \emph{semi-online} case, where the robot not only knows the next input point but is able to ``see'' the future input points included in the disk with radius $R$ around the robot, a path of length $(5.03 + O(1/R))s$ can be computed.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-022000
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518131
Other: Local-ID: C1256428004B93B8-8CFC6B3E07DEFA8BC12569FA003ED4B1-Leejhc2000
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Saarbrücken,Germany
Start-/End Date: 2000

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)
Source Genre: Proceedings
 Creator(s):
Paterson, Mike, Editor
Affiliations:
-
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 314 - 325 Identifier: -

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 1879 Sequence Number: - Start / End Page: - Identifier: -