Watchman routes for lines and line segments

DOI10.1016/j.comgeo.2013.11.008zbMath1302.90174OpenAlexW2067096513MaRDI QIDQ2445196

Paweł Żyliński, Joseph S. B. Mitchell, Adrian Dumitrescu

Publication date: 14 April 2014

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

Full work available at URL: https://doi.org/10.1016/j.comgeo.2013.11.008

zbMATH Keywords

dynamic programmingNP-hardnesswatchman route

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27) Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

An improved algorithm for computing a shortest watchman route for lines ⋮ Reachable region query and its applications ⋮ THE MINIMUM GUARDING TREE PROBLEM ⋮ The searchlight problem for road networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Watchman tours for polygons with holes
• Complexity of minimum corridor guarding problems
• Guarding a set of line segments in the plane
• Cooperative mobile guards in grids
• On gallery watchmen in grids
• Optimum watchman routes
• The Steiner problem with edge lengths 1 and 2
• The Euclidean traveling salesman problem is NP-complete
• A combinatorial theorem in plane geometry
• Illuminating disjoint line segments in the plane
• The traveling salesmanpProblem for lines in the plane
• Fast computation of shortest watchman routes in simple polygons
• Finding the shortest watchman route in a simple polygon
• Covering grids and orthogonal polygons with periscope guards
• A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
• Minimization of the Maximum Distance between the Two Guards Patrolling a Polygonal Region
• Coverage with k-Transmitters in the Presence of Obstacles
• Touring a sequence of polygons
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
• Computing a shortest watchman path in a simple polygon in polynomial-time
• On Steiner’s Problem with Rectilinear Distance
• Approximating Watchman Routes
• A tight bound on approximating arbitrary metrics by tree metrics
• Illumination in the presence of opaque line segments in the plane

This page was built for publication: Watchman routes for lines and line segments