Shortest watchman routes in simple polygons

DOI10.1007/BF02574671MaRDI QIDQ751818zbMATH OpenFDO

Authors Wei-Pang Chin, Simeon C. Ntafos

Publication date 1991

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/131140

zbMATH Keywords

polynomial-time algorithmsimple polygonsNP- hardwatchman-route problem

Mathematics Subject Classification ID

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

Recommendations

• Finding the shortest watchman route in a simple polygon
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• Approximation algorithms for the watchman route and zookeeper's problems.
• Approximating a shortest watchman route
• Optimum watchman routes

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Optimum watchman routes

Cited in

(41)

• The traveling salesmanpProblem for lines in the plane
• Optimum watchman routes
• Online algorithms for searching and exploration in the plane
• scientific article; zbMATH DE number 426139 (Why is no real title available?)
• Watchman routes under limited visibility
• Query-point visibility constrained shortest paths in simple polygons
• Approximating a shortest watchman route
• Finding shortest safari routes in simple polygons
• \(k\)-Transmitter watchman routes
• Minimum-link watchman tours
• The robber route problem
• An improved algorithm for computing a shortest watchman route for lines
• Approximation algorithms for the two-watchman route in a simple polygon
• Concerning the time bounds of existing shortest watchman route algorithms
• Computing a shortest watchman path in a simple polygon in polynomial-time
• Performance bounds for planning in unknown terrain
• An algorithmic approach to some problems in terrain navigation
• Watchman routes for lines and line segments
• The zookeeper route problem
• Observation routes and external watchman routes
• Minimal link visibility paths inside a simple polygon
• A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
• Multiview visibility estimation for image-based modeling
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
• Solving the Watchman Route Problem with Heuristic Search
• A 2-approximation algorithm for the zookeeper's problem
• Shortest paths in simple polygons with polygon-meet constraints
• Finding the shortest boundary guard of a simple polygon
• Shortest watchman tours in simple polygons under rotated monotone visibility
• Observation routes and external watchman routes
• Watchman tours for polygons with holes
• Optimally computing a shortest weakly visible line segment inside a simple polygon
• Theory and Applications of Models of Computation
• Minimum covering with travel cost
• Fast computation of shortest watchman routes in simple polygons
• On Romeo and Juliet problems: minimizing distance-to-sight
• Watchman routes in the presence of a pair of convex polygons
• Moving an angle around a region
• Touring a sequence of disjoint polygons: complexity and extension
• Complexity of minimum corridor guarding problems
• Touring disjoint polygons problem is NP-hard

This page was built for publication: Shortest watchman routes in simple polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q751818)