The Tourist in the Shopping Arcade

Rudolf Fleischer (Fudan University, China)

Tom Kamphans (Braunschweig University of Technology, Germany)

Rolf Klein (University of Bonn, Germany)

Elmar Langetepe (University of Bonn, Germany)

Gerhard Trippen (University of British Columbia, Canada)

Abstract: A 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*.

Keywords: computational geometry, on-line algorithms, on-line navigation

Categories: F.2, G.2