Exploring the Outer Boundary of a Simple Polygon

Qi WEI  Xiaolin YAO  Luan LIU  Yan ZHANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E104-D   No.7   pp.923-930
Publication Date: 2021/07/01
Publicized: 2021/04/02
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2020EDP7234
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
computational geometry,  online algorithm,  path planning,  exploration,  competitive analysis,  

Full Text: PDF(700.3KB)>>
Buy this Article




Summary: 
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.