A linear-time 2-approximation algorithm for the watchman route problem for simple polygons

DOI10.1016/J.TCS.2007.05.021zbMATH Open1124.68118OpenAlexW2065318495MaRDI QIDQ2382287FDOQ2382287

Authors: Xuehou Tan 

Publication date: 28 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.05.021

Recommendations

• Theory and Applications of Models of Computation
• Approximation algorithms for the watchman route and zookeeper's problems.
• Approximating a shortest watchman route
• Finding the shortest watchman route in a simple polygon
• Shortest watchman routes in simple polygons

zbMATH Keywords

computational geometryapproximation algorithmspolygon visibilitywatchman route problemessential cuts

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Touring a sequence of polygons
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• Visibility and intersection problems in plane geometry
• Optimum watchman routes
• Fast computation of shortest watchman routes in simple polygons
• Finding the shortest watchman route in a simple polygon
• Approximation algorithms for the watchman route and zookeeper's problems.
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
• AN OPTIMAL ALGORITHM FOR THE TWO-GUARD PROBLEM
• Characterizing LR-visibility polygons and related problems
• Finding an approximate minimum-link visibility path inside a simple polygon
• LR-visibility in polygons

Cited In (15)

• The Two-Guard Polygon Walk Problem
• An improved algorithm for computing a shortest watchman route for lines
• Theory and Applications of Models of Computation
• Watchman routes in the presence of a pair of convex polygons
• Shortest watchman tours in simple polygons under rotated monotone visibility
• Touring a sequence of disjoint polygons: complexity and extension
• Observation routes and external watchman routes
• Fast computation of shortest watchman routes in simple polygons
• Approximation algorithms for the two-watchman route in a simple polygon
• Watchman routes for lines and line segments
• Complexity of minimum corridor guarding problems
• Observation routes and external watchman routes
• Approximation algorithms for the watchman route and zookeeper's problems.
• GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST
• Improved exploration of unknown polygons

This page was built for publication: A linear-time 2-approximation algorithm for the watchman route problem for simple polygons

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