Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3382-5 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3384-1
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Lee, Jae-Ha1, Autor           
Cheong, Otfried, Autor
Kwon, Woo-Cheol, Autor
Shin, Sung-Yong, Autor
Chwa, Kyung-Yong, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-022000
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 518131
Anderer: Local-ID: C1256428004B93B8-8CFC6B3E07DEFA8BC12569FA003ED4B1-Leejhc2000
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Saarbrücken,Germany
Start-/Enddatum: 2000

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)
Genre der Quelle: Konferenzband
 Urheber:
Paterson, Mike, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 314 - 325 Identifikator: -

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 1879 Artikelnummer: - Start- / Endseite: - Identifikator: -