Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems
verfasst von : Xuehou Tan, Bo Jiang
Erschienen in: Theory and Applications of Models of Computation
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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. This paper describes a simple method to compute the so-called last step shortest path maps, which were developed to solve this touring polygons problem by Dror et al. (STOC’2003). A major simplification is to avoid the (previous) use of point location algorithms. We obtain an O(kn) time solution to the problem for a sequence of 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. Our results improve upon the previous time bounds roughly by a factor of \(\log n\).
Our new method can be used to improve the running times of two classic problems in computational geometry. We then describe an \(O(n (k + \log n))\) time solution to the safari problem and an \(O(n^3)\) time solution to the watchman route problem, respectively. The last step shortest path maps are further modified, so as to meet a new requirement that the shortest paths between a pair of consecutive convex polygons be contained in another bounding simple polygon.