JUCS - Journal of Universal Computer Science 16(5): 676-685, doi: 10.3217/jucs-016-05-0676
The Tourist in the Shopping Arcade
Rudolf Fleischer‡,
Tom Kamphans§,
Rolf Klein|,
Elmar Langetepe|,
Gerhard Trippen¶‡ Fudan University, Shanghai, China§ Braunschweig University of Technology, Braunschweig, Germany| University of Bonn, Bonn, Germany¶ University of British Columbia, Vancouver, Canada
Corresponding author:
Rudolf Fleischer
(
rudolf@acm.org
)
© Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen. Citation:
Fleischer R, Kamphans T, Klein R, Langetepe E, Trippen G (2010) The Tourist in the Shopping Arcade. JUCS - Journal of Universal Computer Science 16(5): 676-685. https://doi.org/10.3217/jucs-016-05-0676 | ![Open Access](/i/open_access_icon_colour.svg) |
AbstractA tourist is searching for a gift and moves along a shopping arcade until the desired object gets into sight. The location of the corresponding shop is not known in advance. Therefore in this on-line setting the tourist has to make a detour in comparison to an optimal off-line straight line path to the desired object. We can show that there is a strategy for the tourist, so that the path length is never greater than C* times the optimal off-line path length, where C* = 1.059401 . . . holds. Furthermore, there is no strategy that attains a competitive factor smaller than C*.
Keywordscomputational geometry, on-line algorithms, on-line navigation