×

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.)