Touring a sequence of disjoint polygons: complexity and extension

DOI10.1016/j.tcs.2014.06.019zbMath1338.68253OpenAlexW1992272252MaRDI QIDQ300225

Alireza Zarei, Arash Ahadi, Amirhossein Mozafari

Publication date: 27 June 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.06.019

zbMATH Keywords

complexityshortest pathtouring polygons

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Unnamed Item ⋮ Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Shortest watchman routes in simple polygons
• An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
• A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
• Euclidean Shortest Paths
• Touring a sequence of polygons
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• New results on shortest paths in three dimensions
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE

This page was built for publication: Touring a sequence of disjoint polygons: complexity and extension