The tourist in the shopping arcade. (English) Zbl 1216.68315
Summary: 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\dots\) holds. Furthermore, there is no strategy that attains a competitive factor smaller than \(C^{*}\).
MSC:
68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |