Touring polygons: an approximation algorithm

DOI10.1007/978-3-642-35926-2_13MaRDI QIDQ2876565zbMATH OpenOpenAlexFDO

Authors Amirhossein Mozafari, Alireza Zarei

Publication date 19 August 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-35926-2_13

zbMATH Keywords

approximation algorithmcomputational geometryminimum link pathtouring polygons

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Touring convex polygons in polygonal domain fences
• Touring a sequence of polygons
• Touring disjoint polygons problem is NP-hard
• Touring a sequence of disjoint polygons: complexity and extension
• Efficient algorithms for touring a sequence of convex polygons and related problems

Cited in

(8)

• Not all insertion methods yield constant approximate tours in the Euclidean plane
• Touring convex polygons in polygonal domain fences
• Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation
• Touring disjoint polygons problem is NP-hard
• Approximating corridors and tours via restriction and relaxation techniques
• Efficient algorithms for touring a sequence of convex polygons and related problems
• Touring a sequence of disjoint polygons: complexity and extension
• Touring a sequence of polygons

This page was built for publication: Touring polygons: an approximation algorithm

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