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

DOI10.1016/0020-0190(95)00072-KzbMath1022.68624OpenAlexW1997350911MaRDI QIDQ672401

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)

Related Items (6)

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

Cites Work

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

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