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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation algorithms for art gallery problems in polygons
• The Euclidean traveling salesman problem is NP-complete
• Title not available (Why is that?)
• Title not available (Why is that?)
• Touring a sequence of polygons
• Title not available (Why is that?)
• Shortest watchman routes in simple polygons
• Title not available (Why is that?)
• Minimum-link watchman tours
• Optimum watchman routes
• On Steiner trees for bounded point sets
• 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
• How Long Can a Euclidean Traveling Salesman Tour Be?

Cited In (14)

• Touring a sequence of polygons
• On Romeo and Juliet problems: minimizing distance-to-sight
• Title not available (Why is that?)
• On the shortest separating cycle
• Shortest watchman tours in simple polygons under rotated monotone visibility
• Minimum-link watchman tours
• Touring a sequence of disjoint polygons: complexity and extension
• How to Keep an Eye on Small Things
• Approximation algorithms for the two-watchman route in a simple polygon
• Watchman routes for lines and line segments
• Observation routes and external watchman routes
• Title not available (Why is that?)
• On Romeo and Juliet Problems: Minimizing Distance-to-Sight.
• \(k\)-Transmitter watchman routes

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)