Approximation algorithms for the watchman route and zookeeper's problems.
From MaRDI portal
Publication:1427191
DOI10.1016/S0166-218X(03)00451-7zbMath1066.68143OpenAlexW2052861240MaRDI QIDQ1427191
Publication date: 14 March 2004
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00451-7
Computational geometryApproximation algorithmsZookeeper's problemReflection principleWatchman route problem
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (10)
A 2-approximation algorithm for the zookeeper's problem ⋮ Approximating the Metric TSP in Linear Time ⋮ A linear-time 2-approximation algorithm for the watchman route problem for simple polygons ⋮ Shortest paths in simple polygons with polygon-meet constraints ⋮ An Improved On-line Strategy for Exploring Unknown Polygons ⋮ Improved exploration of unknown polygons ⋮ Complexity of minimum corridor guarding problems ⋮ Approximating the metric TSP in linear time ⋮ On finding a shortest isothetic path and its monotonicity inside a digital object ⋮ Query-point visibility constrained shortest paths in simple polygons
Cites Work
- Finding an approximate minimum-link visibility path inside a simple polygon
- LR-visibility in polygons
- Visibility and intersection problems in plane geometry
- An approximative solution to the Zookeeper's problem
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Optimum watchman routes
- An optimal visibility graph algorithm for triangulated simple polygons
- Triangulating a simple polygon in linear time
- The zookeeper route problem
- Practical methods for approximating shortest paths on a convex polytope in \(\mathbb{R}^3\)
- Shortest zookeeper's routes in simple polygons
- Fast computation of shortest watchman routes in simple polygons
- 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"
This page was built for publication: Approximation algorithms for the watchman route and zookeeper's problems.
