Minimum-link watchman tours

DOI10.1016/S0020-0190(02)00502-1zbMATH Open1173.68757OpenAlexW1973102563MaRDI QIDQ1007602FDOQ1007602

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

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

computational geometryapproximation algorithmspolygonsNP-completelink distancewatchman route

Mathematics Subject Classification ID

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

Recommendations

• Approximating watchman routes
• Finding an approximate minimum-link visibility path inside a simple polygon
• Watchman routes for lines and line segments
• Watchman tours for polygons with holes
• Optimum watchman routes

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• 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
• Fast computation of shortest watchman routes in simple polygons
• Finding an approximate minimum-link visibility path inside a simple polygon
• Finding the shortest watchman route in a simple polygon
• Minimal link visibility paths inside a simple polygon
• On the complexity of locating linear facilities in the plane
• Optimum watchman routes
• Shortest watchman routes in simple polygons

Cited in

(19)

• scientific article; zbMATH DE number 177562 (Why is no real title available?)
• Covering paths for planar point sets
• On Covering Points with Minimum Turns
• On the shortest separating cycle
• Rainbow polygons for colored point sets in the plane
• The complexity of drawing a graph in a polygonal region
• Orthogonal segment stabbing
• FPT-algorithms for minimum-bends tours
• Delineating boundaries for imprecise regions
• The complexity of drawing a graph in a polygonal region
• On finding a shortest isothetic path and its monotonicity inside a digital object
• Taming the knight's tour: minimizing turns and crossings
• Watchman tours for polygons with holes
• Traversing a set of points with a minimum number of turns
• Approximating watchman routes
• On the approximability of covering points by lines and related problems
• Is it FPT to cover points with tours on minimum number of bends (errata)?
• Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
• Online exploration outside a convex obstacle

This page was built for publication: Minimum-link watchman tours

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