An improved algorithm for computing a shortest watchman route for lines

DOI10.1016/j.ipl.2017.11.011zbMath1423.68557OpenAlexW2775016279MaRDI QIDQ1685027

Bo Jiang, Xue-Hou Tan

Publication date: 13 December 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2017.11.011

zbMATH Keywords

dynamic programmingshortest pathscomputational geometrywatchman route problem

Mathematics Subject Classification ID

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

Related Items (1)

Graphs with equal domination and covering numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Optimum watchman routes
• The traveling salesmanpProblem for lines in the plane
• Fast computation of shortest watchman routes in simple polygons
• Watchman routes for lines and line segments
• Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems
• Touring a sequence of polygons
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"

This page was built for publication: An improved algorithm for computing a shortest watchman route for lines