Minimum-link watchman tours

DOI10.1016/S0020-0190(02)00502-1zbMath1173.68757OpenAlexW1973102563MaRDI QIDQ1007602

Esther M. Arkin, Christine D. Piatko, Joseph S. B. Mitchell

Publication date: 23 March 2009

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00502-1

zbMATH Keywords

NP-completecomputational geometryapproximation algorithmspolygonslink distancewatchman route

Mathematics Subject Classification ID

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

Related Items

The Complexity of Drawing a Graph in a Polygonal Region, Online exploration outside a convex obstacle, Is It FPT to Cover Points with Tours on Minimum Number of Bends (Errata)?, Watchman tours for polygons with holes, On the approximability of covering points by lines and related problems, The complexity of drawing a graph in a polygonal region, Improved parameterized algorithms for minimum link-length rectilinear spanning path problem, FPT-ALGORITHMS FOR MINIMUM-BENDS TOURS, On finding a shortest isothetic path and its monotonicity inside a digital object, Traversing a set of points with a minimum number of turns, Covering paths for planar point sets, Delineating boundaries for imprecise regions, Orthogonal segment stabbing, Rainbow polygons for colored point sets in the plane, On Covering Points with Minimum Turns, On the shortest separating cycle, Taming the knight's tour: minimizing turns and crossings

Cites Work

• Unnamed Item
• Finding an approximate minimum-link visibility path inside a simple polygon
• Shortest watchman routes in simple polygons
• Optimum watchman routes
• Fast computation of shortest watchman routes in simple polygons
• Finding the shortest watchman route in a simple polygon
• On the complexity of locating linear facilities in the plane
• Minimal link visibility paths inside a simple polygon
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
• Concerning the time bounds of existing shortest watchman route algorithms