The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Nous étudions un problème en ligne d'un robot explorant la limite extérieure d'un polygone simple inconnu P. Le robot démarre à partir d'un sommet spécifié s et fait une tournée d'exploration à l'extérieur P. Il doit voir tous les points de la limite extérieure du polygone et revenir au début. Nous fournissons des limites inférieures et supérieures sur le rapport entre la distance parcourue par le robot et la longueur du chemin le plus court. Nous considérons P dans deux scénarios : polygone convexe et polygone concave. Pour le premier scénario, nous prouvons une borne inférieure de 5 et proposons une stratégie compétitive à 23.78. Pour le deuxième scénario, nous prouvons une borne inférieure de 5.03 et proposons une stratégie compétitive de 26.5.
Qi WEI
Liaoning Normal University
Xiaolin YAO
Dalian Neusoft University of Information
Luan LIU
Liaoning Normal University
Yan ZHANG
Liaoning Normal University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Qi WEI, Xiaolin YAO, Luan LIU, Yan ZHANG, "Exploring the Outer Boundary of a Simple Polygon" in IEICE TRANSACTIONS on Information,
vol. E104-D, no. 7, pp. 923-930, July 2021, doi: 10.1587/transinf.2020EDP7234.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020EDP7234/_p
Copier
@ARTICLE{e104-d_7_923,
author={Qi WEI, Xiaolin YAO, Luan LIU, Yan ZHANG, },
journal={IEICE TRANSACTIONS on Information},
title={Exploring the Outer Boundary of a Simple Polygon},
year={2021},
volume={E104-D},
number={7},
pages={923-930},
abstract={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.},
keywords={},
doi={10.1587/transinf.2020EDP7234},
ISSN={1745-1361},
month={July},}
Copier
TY - JOUR
TI - Exploring the Outer Boundary of a Simple Polygon
T2 - IEICE TRANSACTIONS on Information
SP - 923
EP - 930
AU - Qi WEI
AU - Xiaolin YAO
AU - Luan LIU
AU - Yan ZHANG
PY - 2021
DO - 10.1587/transinf.2020EDP7234
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E104-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2021
AB - 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.
ER -