Touring a sequence of disjoint polygons: complexity and extension

DOI10.1016/J.TCS.2014.06.019MaRDI QIDQ300225zbMATH OpenOpenAlexFDO

Authors A. Ahadi, Amirhossein Mozafari, Alireza Zarei

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Efficient algorithms for touring a sequence of convex polygons and related problems
• Touring polygons: an approximation algorithm
• Touring a sequence of polygons
• Touring disjoint polygons problem is NP-hard
• scientific article; zbMATH DE number 1786499
• The polygon exploration problem
• Touring convex polygons in polygonal domain fences
• Polynomial-time algorithms for the touring rays and related problems
• Watchman tours for polygons with holes
• The complexity of computing minimum separating polygons

Cites work

• A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
• An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• Euclidean shortest paths. Exact or approximate algorithms.
• scientific article; zbMATH DE number 1555972 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• New results on shortest paths in three dimensions
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
• Shortest watchman routes in simple polygons
• Touring a sequence of polygons

Cited in

(6)

• Touring convex polygons in polygonal domain fences
• Touring disjoint polygons problem is NP-hard
• Touring polygons: an approximation algorithm
• Efficient algorithms for touring a sequence of convex polygons and related problems
• Touring a sequence of polygons
• scientific article; zbMATH DE number 7151640 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q300225)