Minimum-link watchman tours

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

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

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

zbMATH Keywords

computational geometryapproximation algorithmspolygonsNP-completelink distancewatchman route

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (18)

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

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)