Watchman routes under limited visibility

DOI10.1016/0925-7721(92)90014-JzbMath0772.68107OpenAlexW4213368447MaRDI QIDQ1188285

Simeon C. Ntafos

Publication date: 13 August 1992

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(92)90014-j

zbMATH Keywords

path planningpolynomial approximation scheme\(d\)-sweeper problem\(d\)-watchman problemsafari route problem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30)

Related Items

Optimally computing a shortest weakly visible line segment inside a simple polygon, Approximation algorithms for the Geometric Covering Salesman Problem, Off-line exploration of rectangular cellular environments with a rectangular obstacle, Shortest paths in simple polygons with polygon-meet constraints, Online exploration outside a convex obstacle, \(\alpha\)-kernel problem with fuzzy visibility, Worst-case optimal exploration of terrains with obstacles, Optimality and competitiveness of exploring polygons by mobile robots, Observation routes and external watchman routes, On-line exploration of rectangular cellular environments with a rectangular hole, Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems, On finding a shortest isothetic path and its monotonicity inside a digital object, An optimal algorithm for finding the edge visibility polygon under limited visibility, EXISTENCE AND COMPUTATION OF TOURS THROUGH IMPRECISE POINTS, Query-point visibility constrained shortest paths in simple polygons, Path optimization with limited sensing ability, A sequential convex programming algorithm for minimizing a sum of Euclidean norms with non-convex constraints, Finding shortest safari routes in simple polygons, Advice complexity of treasure hunt in geometric terrains, GUARD PLACEMENT FOR MAXIMIZING L-VISIBILITY EXTERIOR TO A CONVEX POLYGON, Approximation algorithms for lawn mowing and milling, How to Keep an Eye on Small Things, Performance bounds for planning in unknown terrain, Competitive on-line coverage of grid environments by a mobile robot

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Shortest watchman routes in simple polygons
• The robber route problem
• Optimum watchman routes
• The Euclidean traveling salesman problem is NP-complete
• Hamilton Paths in Grid Graphs
• The NP-completeness column: An ongoing guide