|
|
|
|
The Tourist in the Shopping Arcade
|
|
|
|
|
|
|
|
نویسنده
|
Fleischer Rudolf ,Kamphans Tom ,Klein Rolf ,Langetepe Elmar ,Trippen Gerhard
|
|
منبع
|
journal of universal computer science - 2010 - دوره : 16 - شماره : 5 - صفحه:676 -685
|
|
چکیده
|
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*.
|
|
کلیدواژه
|
Computational geometry ,on-line algorithms ,on-line navigation.
|
|
آدرس
|
Fudan University, China, Braunschweig University of Technology, Germany, University of Bonn, Germany, University of Bonn, Germany, University of British Columbia, Canada
|
|
پست الکترونیکی
|
gerhard.trippen@sauder.ubc.ca
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|