de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Approximation of Curvature-constrained Shortest Paths through a Sequence of Points

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44897

Lee,  Jae-Ha
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-3382-5
Zusammenfassung
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.