Optimal on-line algorithms for walking with minimum number of turns in unknown streets

Ghosh, Subir Kumar ; Saluja, Sanjeev (1997) Optimal on-line algorithms for walking with minimum number of turns in unknown streets Computational Geometry, 8 (5). pp. 241-266. ISSN 0925-7721

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1016/S0925-7721(97)00003-5

Abstract

A simple polygon P with two distinguished vertices s and t is said to be a street if the clockwise and counterclockwise boundary of P from s to t are mutually weakly visible. We consider the problem of traversing a path from s to t in an unknown street P for a mobile robot with on-board vision system such that the number of links in the path is as small as possible. To our knowledge, this problem has not been studied before. We present an algorithm for this problem that requires at most 2m - 1 links to reach from s to t, where m denotes the link distance between s and t in P. Hence the competitive ratio of our algorithm is 2-1/m. We also show that any on-line algorithm for the above problem will require 2m - 1 links in the worst case which establishes that our algorithm is optimal. We next consider the above problem for the special case when P is a rectilinear street and the path is required to be a rectilinear path. We propose an algorithm for this problem that requires at most m + 1 links to reach from s to t, where m denotes the rectilinear link distance between s and t in P. Hence the competitive ratio of our algorithm is 1+1/m. We also show that any on-line algorithm for this problem will require m + 1 links in the worst case which establishes that our algorithm is optimal.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:On-line Algorithm; Link Path; Competitive Ratio; Rectilinear Path; Street
ID Code:76279
Deposited On:31 Dec 2011 08:57
Last Modified:31 Dec 2011 08:57

Repository Staff Only: item control page