Minimal link visibility paths inside a simple polygon

DOI10.1016/0925-7721(93)90027-4MaRDI QIDQ2367125zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 23 August 1993

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(93)90027-4

zbMATH Keywords

computational geometryvisibility\(NP\)-hard

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Finding an approximate minimum-link visibility path inside a simple polygon
• Minimum-link watchman tours
• NP-harte Probleme für minimale Polygonüberdeckungen. (NP-hard problems for minimal polygon coverings)
• On the complexity of minimum-link path problems

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A linear algorithm for computing the visibility polygon from a point
• A linear time algorithm for minimum link paths inside a simple polygon
• An Optimal Algorithm for Finding the Kernel of a Polygon
• An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
• Computational complexity of art gallery problems
• Computing the link center of a simple polygon
• Euclidean shortest paths in the presence of rectilinear barriers
• On the Complexity of Some Common Geometric Location Problems
• Optimum watchman routes
• Shortest watchman routes in simple polygons

Cited in

(7)

• Minimum-link watchman tours
• Geometric Secluded Paths and Planar Satisfiability
• On the complexity of minimum-link path problems
• MINIMUM SEPARATION IN WEIGHTED SUBDIVISIONS
• Single-Point Visibility Constraint Minimum Link Paths in Simple Polygons
• Finding a shortest Hamiltonian path inside a simple polygon
• Finding an approximate minimum-link visibility path inside a simple polygon

This page was built for publication: Minimal link visibility paths inside a simple polygon

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