Watchman tours for polygons with holes

DOI10.1016/J.COMGEO.2012.02.001zbMATH Open1239.65016OpenAlexW2024874686MaRDI QIDQ419503FDOQ419503

Authors Adrian Dumitrescu, Csaba D. Tóth 

Publication date 18 May 2012

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2012.02.001

zbMATH Keywords

approximation algorithmNP-hardnessminimum watchman tourpolygon with holeswatchman tours

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Approximating watchman routes
• Minimum-link watchman tours
• Shortest watchman routes in simple polygons
• Optimum watchman routes
• Watchman routes in the presence of a pair of convex polygons

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1424293 (Why is no real title available?)
• scientific article; zbMATH DE number 1424303 (Why is no real title available?)
• scientific article; zbMATH DE number 1424307 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• Approximation algorithms for art gallery problems in polygons
• Approximation algorithms for lawn mowing and milling
• Fast computation of shortest watchman routes in simple polygons
• Finding the shortest watchman route in a simple polygon
• How Long Can a Euclidean Traveling Salesman Tour Be?
• Minimum-link watchman tours
• On Steiner trees for bounded point sets
• Optimal Exploration of Terrains with Obstacles
• Optimum watchman routes
• Ray shooting on triangles in 3-space
• Ray shooting, depth orders and hidden surface removal
• Shortest watchman routes in simple polygons
• The Euclidean traveling salesman problem is NP-complete
• The shortest path and the shortest road through n points
• Touring a sequence of polygons

Cited in

(14)

• scientific article; zbMATH DE number 177562 (Why is no real title available?)
• How to Keep an Eye on Small Things
• On the shortest separating cycle
• \(k\)-Transmitter watchman routes
• Minimum-link watchman tours
• Approximation algorithms for the two-watchman route in a simple polygon
• Watchman routes for lines and line segments
• Gender-aware facility location in multi-gender world
• Shortest watchman tours in simple polygons under rotated monotone visibility
• Touring a sequence of polygons
• Observation routes and external watchman routes
• On Romeo and Juliet problems: minimizing distance-to-sight
• On Romeo and Juliet problems: minimizing distance-to-sight
• Touring a sequence of disjoint polygons: complexity and extension

This page was built for publication: Watchman tours for polygons with holes

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