Watchman tours for polygons with holes

DOI10.1016/j.comgeo.2012.02.001zbMath1239.65016OpenAlexW2024874686MaRDI QIDQ419503

Csaba D. Tóth, Adrian Dumitrescu

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)

Related Items (7)

Unnamed Item ⋮ \(k\)-Transmitter watchman routes ⋮ Watchman routes for lines and line segments ⋮ On the shortest separating cycle ⋮ On Romeo and Juliet problems: minimizing distance-to-sight ⋮ On Romeo and Juliet Problems: Minimizing Distance-to-Sight. ⋮ How to Keep an Eye on Small Things

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Shortest watchman routes in simple polygons
• Approximation algorithms for art gallery problems in polygons
• Minimum-link watchman tours
• Optimum watchman routes
• On Steiner trees for bounded point sets
• The Euclidean traveling salesman problem is NP-complete
• Ray shooting, depth orders and hidden surface removal
• Fast computation of shortest watchman routes in simple polygons
• Finding the shortest watchman route in a simple polygon
• Approximation algorithms for lawn mowing and milling
• Ray shooting on triangles in 3-space
• The shortest path and the shortest road through n points
• Optimal Exploration of Terrains with Obstacles
• Touring a sequence of polygons
• How Long Can a Euclidean Traveling Salesman Tour Be?

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