Finding an approximate minimum-link visibility path inside a simple polygon

DOI10.1016/0020-0190(95)00072-KMaRDI QIDQ672401zbMATH OpenOpenAlexFDO

Authors Juan-Miguel Gracia

Publication date 28 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(95)00072-k

zbMATH Keywords

computational geometryapproximation algorithmssimple polygonminimum link pathvisibility path

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Minimum-link watchman tours
• Minimal link visibility paths inside a simple polygon
• Approximating watchman routes
• Computing a shortest watchman path in a simple polygon in polynomial-time
• Approximation algorithms for the watchman route and zookeeper's problems.

Cites work

• A linear time algorithm for minimum link paths inside a simple polygon
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Computing minimum length paths of a given homotopy class
• Computing the visibility polygon from a convex set and related problems
• Minimal link visibility paths inside a simple polygon
• Minimum Cuts for Circular-Arc Graphs

Cited in

(7)

• Minimum-link watchman tours
• Fast computation of shortest watchman routes in simple polygons
• Approximation algorithms for the watchman route and zookeeper's problems.
• A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
• MINIMUM SEPARATION IN WEIGHTED SUBDIVISIONS
• Single-Point Visibility Constraint Minimum Link Paths in Simple Polygons
• Finding a shortest Hamiltonian path inside a simple polygon

This page was built for publication: Finding an approximate minimum-link visibility path inside a simple polygon

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