The search functionality is under construction.

The search functionality is under construction.

Given a sequence of *k* convex polygons in the plane, a start point *s*, and a target point *t*, we seek a shortest path that starts at *s*, visits in order each of the polygons, and ends at *t*. We revisit this *touring polygons problem*, which was introduced by Dror et al. (STOC 2003), by describing a simple method to compute the so-called *last step shortest path maps*, one per polygon. We obtain an *O*(*kn*)-time solution to the problem for a sequence of pairwise disjoint convex polygons and an *O*(*k*^{2}*n*)-time solution for possibly intersecting convex polygons, where *n* is the total number of vertices of all polygons. A major simplification is made on the operation of locating query points in the last step shortest path maps. Our results improve upon the previous time bounds roughly by a factor of log *n*.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.5 pp.772-777

- Publication Date
- 2018/05/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E101.A.772

- Type of Manuscript
- PAPER

- Category
- Algorithms and Data Structures

Xuehou TAN

Tokai University

Bo JIANG

Dalian Maritime 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.

Copy

Xuehou TAN, Bo JIANG, "The Touring Polygons Problem Revisited" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 5, pp. 772-777, May 2018, doi: 10.1587/transfun.E101.A.772.

Abstract: Given a sequence of *k* convex polygons in the plane, a start point *s*, and a target point *t*, we seek a shortest path that starts at *s*, visits in order each of the polygons, and ends at *t*. We revisit this *touring polygons problem*, which was introduced by Dror et al. (STOC 2003), by describing a simple method to compute the so-called *last step shortest path maps*, one per polygon. We obtain an *O*(*kn*)-time solution to the problem for a sequence of pairwise disjoint convex polygons and an *O*(*k*^{2}*n*)-time solution for possibly intersecting convex polygons, where *n* is the total number of vertices of all polygons. A major simplification is made on the operation of locating query points in the last step shortest path maps. Our results improve upon the previous time bounds roughly by a factor of log *n*.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.772/_p

Copy

@ARTICLE{e101-a_5_772,

author={Xuehou TAN, Bo JIANG, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={The Touring Polygons Problem Revisited},

year={2018},

volume={E101-A},

number={5},

pages={772-777},

abstract={Given a sequence of *k* convex polygons in the plane, a start point *s*, and a target point *t*, we seek a shortest path that starts at *s*, visits in order each of the polygons, and ends at *t*. We revisit this *touring polygons problem*, which was introduced by Dror et al. (STOC 2003), by describing a simple method to compute the so-called *last step shortest path maps*, one per polygon. We obtain an *O*(*kn*)-time solution to the problem for a sequence of pairwise disjoint convex polygons and an *O*(*k*^{2}*n*)-time solution for possibly intersecting convex polygons, where *n* is the total number of vertices of all polygons. A major simplification is made on the operation of locating query points in the last step shortest path maps. Our results improve upon the previous time bounds roughly by a factor of log *n*.},

keywords={},

doi={10.1587/transfun.E101.A.772},

ISSN={1745-1337},

month={May},}

Copy

TY - JOUR

TI - The Touring Polygons Problem Revisited

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 772

EP - 777

AU - Xuehou TAN

AU - Bo JIANG

PY - 2018

DO - 10.1587/transfun.E101.A.772

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E101-A

IS - 5

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - May 2018

AB - Given a sequence of *k* convex polygons in the plane, a start point *s*, and a target point *t*, we seek a shortest path that starts at *s*, visits in order each of the polygons, and ends at *t*. We revisit this *touring polygons problem*, which was introduced by Dror et al. (STOC 2003), by describing a simple method to compute the so-called *last step shortest path maps*, one per polygon. We obtain an *O*(*kn*)-time solution to the problem for a sequence of pairwise disjoint convex polygons and an *O*(*k*^{2}*n*)-time solution for possibly intersecting convex polygons, where *n* is the total number of vertices of all polygons. A major simplification is made on the operation of locating query points in the last step shortest path maps. Our results improve upon the previous time bounds roughly by a factor of log *n*.

ER -