Fast computation of shortest watchman routes in simple polygons
From MaRDI portal
Publication:1607078
DOI10.1016/S0020-0190(00)00146-0zbMath1003.68174OpenAlexW1974433908WikidataQ29304368 ScholiaQ29304368MaRDI QIDQ1607078
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
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