IEICE TRANSACTIONS on Information
Online Vertex Exploration Problems in a Simple Polygon
Summary :
This paper considers online vertex exploration problems in a simple polygon where starting from a point in the inside of a simple polygon, a searcher is required to explore a simple polygon to visit all its vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm.
- Publication
- IEICE TRANSACTIONS on Information Vol.E96-D No.3 pp.489-497
- Publication Date
- 2013/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E96.D.489
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Yuya HIGASHIKAWA, Naoki KATOH, "Online Vertex Exploration Problems in a Simple Polygon" in IEICE TRANSACTIONS on Information,
vol. E96-D, no. 3, pp. 489-497, March 2013, doi: 10.1587/transinf.E96.D.489.
Abstract: This paper considers online vertex exploration problems in a simple polygon where starting from a point in the inside of a simple polygon, a searcher is required to explore a simple polygon to visit all its vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.489/_p
Copy
@ARTICLE{e96-d_3_489,
author={Yuya HIGASHIKAWA, Naoki KATOH, },
journal={IEICE TRANSACTIONS on Information},
title={Online Vertex Exploration Problems in a Simple Polygon},
year={2013},
volume={E96-D},
number={3},
pages={489-497},
abstract={This paper considers online vertex exploration problems in a simple polygon where starting from a point in the inside of a simple polygon, a searcher is required to explore a simple polygon to visit all its vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm.},
keywords={},
doi={10.1587/transinf.E96.D.489},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Online Vertex Exploration Problems in a Simple Polygon
T2 - IEICE TRANSACTIONS on Information
SP - 489
EP - 497
AU - Yuya HIGASHIKAWA
AU - Naoki KATOH
PY - 2013
DO - 10.1587/transinf.E96.D.489
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2013
AB - This paper considers online vertex exploration problems in a simple polygon where starting from a point in the inside of a simple polygon, a searcher is required to explore a simple polygon to visit all its vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm.
ER -
English
