首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:The Tourist in the Shopping Arcade
  • 本地全文:下载
  • 作者:Rudolf Fleischer (Fudan University ; China) Tom Kamphans (Braunschweig University of Technology ; Germany) Rolf Klein (University of Bonn
  • 期刊名称:Journal of Universal Computer Science
  • 印刷版ISSN:0948-6968
  • 出版年度:2010
  • 卷号:16
  • 期号:5
  • 出版社:Graz University of Technology and Know-Center
  • 摘要:

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

  • 关键词:computational geometry, on-line algorithms, on-line navigation
国家哲学社会科学文献中心版权所有