Shortest watchman routes in simple polygons

DOI10.1007/BF02574671zbMath0715.68037MaRDI QIDQ751818

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)

Related Items

Optimally computing a shortest weakly visible line segment inside a simple polygon, Minimal link visibility paths inside a simple polygon, Touring a sequence of disjoint polygons: complexity and extension, Moving an angle around a region, Concerning the time bounds of existing shortest watchman route algorithms, A 2-approximation algorithm for the zookeeper's problem, Computing a shortest watchman path in a simple polygon in polynomial-time, Multiview visibility estimation for image-based modeling, Optimum watchman routes, Shortest paths in simple polygons with polygon-meet constraints, An algorithmic approach to some problems in terrain navigation, \(k\)-Transmitter watchman routes, Watchman tours for polygons with holes, Observation routes and external watchman routes, The robber route problem, Minimum covering with travel cost, Complexity of minimum corridor guarding problems, Online algorithms for searching and exploration in the plane, Watchman routes under limited visibility, Query-point visibility constrained shortest paths in simple polygons, The zookeeper route problem, CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES", Minimum-link watchman tours, Finding shortest safari routes in simple polygons, Watchman routes in the presence of a pair of convex polygons, Touring Disjoint Polygons Problem Is NP-Hard, The traveling salesmanpProblem for lines in the plane, Solving the Watchman Route Problem with Heuristic Search, Fast computation of shortest watchman routes in simple polygons, Performance bounds for planning in unknown terrain

Cites Work

• Unnamed Item
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Optimum watchman routes
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon