Fast computation of shortest watchman routes in simple polygons

DOI10.1016/S0020-0190(00)00146-0zbMath1003.68174OpenAlexW1974433908WikidataQ29304368 ScholiaQ29304368MaRDI QIDQ1607078

Xue-Hou Tan

Publication date: 25 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(00)00146-0

zbMATH Keywords

watchman route problem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Algorithms for approximation of functions (65D15)

Related Items

A 2-approximation algorithm for the zookeeper's problem ⋮ A linear-time 2-approximation algorithm for the watchman route problem for simple polygons ⋮ The touring rays and related problems ⋮ Improved exploration of unknown polygons ⋮ An improved algorithm for computing a shortest watchman route for lines ⋮ \(k\)-Transmitter watchman routes ⋮ Watchman tours for polygons with holes ⋮ Observation routes and external watchman routes ⋮ Complexity of minimum corridor guarding problems ⋮ Watchman routes for lines and line segments ⋮ Approximation algorithms for the watchman route and zookeeper's problems. ⋮ Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems ⋮ Open Guard Edges and Edge Guards in Simple Polygons ⋮ THE TRAVELING SALESMAN PROBLEM FOR LINES AND RAYS IN THE PLANE ⋮ Polynomial-time algorithms for the touring rays and related problems ⋮ Minimum-link watchman tours ⋮ Finding shortest safari routes in simple polygons ⋮ Optimal placement of base stations in border surveillance using limited capacity drones ⋮ How to Keep an Eye on Small Things

Cites Work

• Finding an approximate minimum-link visibility path inside a simple polygon
• Shortest watchman routes in simple polygons
• Optimum watchman routes
• Finding the shortest watchman route in a simple polygon
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
• Concerning the time bounds of existing shortest watchman route algorithms
• Unnamed Item