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
Kami menyiasat masalah dalam talian robot yang meneroka sempadan luar poligon mudah yang tidak diketahui P. Robot bermula dari puncak tertentu s dan berjalan dalam lawatan penerokaan di luar P. Ia perlu melihat semua titik sempadan luar poligon dan kembali ke permulaan. Kami menyediakan sempadan bawah dan atas pada nisbah jarak yang dilalui oleh robot berbanding dengan panjang laluan terpendek. Kami mengambil kira P dalam dua senario: poligon cembung dan poligon cekung. Untuk senario pertama, kami membuktikan sempadan bawah 5 dan mencadangkan strategi persaingan 23.78. Untuk senario kedua, kami membuktikan had bawah 5.03 dan mencadangkan strategi persaingan 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.
Salinan
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
Salinan
@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},}
Salinan
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 -