Minimum-link watchman tours

DOI10.1016/S0020-0190(02)00502-1MaRDI QIDQ1007602zbMATH OpenOpenAlexFDO

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

approximation algorithmscomputational geometrylink distanceNP-completepolygonswatchman 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

• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Concerning the time bounds of existing shortest watchman route algorithms
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
• 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
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• 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

(22)

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

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)