
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

The Touring Polygons Problem Revisited
Xuehou TAN Bo JIANG
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E101A
No.5
pp.772777 Publication Date: 2018/05/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E101.A.772
Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: shortest path, touring polygons problem, last step shortest path map, convex polygons,
Full Text: PDF(810KB) >>Buy this Article
Summary:
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 socalled 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.

