Tight analysis of a self-approaching strategy for the online kernel-search problem

被引：3

作者：

Lee, JH ^{[1
]}

Chwa, KY ^{[1
]}

机构：

[1] Korea Adv Inst Sci & Technol, Dept Comp Sci, Yusong Gu, Taejon 305701, South Korea

来源：

INFORMATION PROCESSING LETTERS | 1999年 / 69卷 / 01期

关键词：

computational geometry; online algorithm; star-shaped polygon;

D O I：

10.1016/S0020-0190(98)00191-4

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The online kernel-search problem is for a mobile robot with 360 degrees degree vision to move from a starting point to the closest kernel point within an unknown star-shaped polygon. Icking and Klein (1991, 1997) presented a simple strategy, called CAB, and showed that CAB is 5.331-competitive. In this paper we show that CAB is (pi + 1)-competitive, which is a tight analysis of it. (C) 1999 Published by Elsevier Science B.V. All rights reserved.

引用

页码：39 / 45

页数：7

共 8 条

[1]

Hoffmann F, 1997, PROCEEDINGS OF THE EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P166

[2]

Icking C., 1995, Proceedings of the Eleventh Annual Symposium on Computational Geometry, P258, DOI 10.1145/220279.220307

[3]

ICKING C, 1997, 211 FERN U

[4]

ICKING C, IN PRESS MATH P CAMB

[5]

KLEIN R, 1991, PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, P304, DOI 10.1109/SFCS.1991.185383

[6]

LEE JH, 1997, P 13 ANN ACM S COMP, P427

[7]

Papadimitriou C.H., 1989, LECT NOTES COMPUTER, V372, P610

[8] CURVES WITH INCREASING CHORDS [J].

ROTE, G .

MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1994, 115 :1-12

← 1 →