For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Exploring the Outer Boundary of a Simple Polygon
Qi WEI Xiaolin YAO Luan LIU Yan ZHANG
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2021/07/01
Online ISSN: 1745-1361
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
computational geometry, online algorithm, path planning, exploration, competitive analysis,
Full Text: PDF(700.3KB)>>
We investigate an online problem of a robot exploring the outer boundary of an unknown simple polygon P. The robot starts from a specified vertex s and walks an exploration tour outside P. It has to see all points of the polygon's outer boundary and to return to the start. We provide lower and upper bounds on the ratio of the distance traveled by the robot in comparison to the length of the shortest path. We consider P in two scenarios: convex polygon and concave polygon. For the first scenario, we prove a lower bound of 5 and propose a 23.78-competitive strategy. For the second scenario, we prove a lower bound of 5.03 and propose a 26.5-competitive strategy.