Finding the shortest watchman route in a simple polygon

DOI10.1007/PL00009467MaRDI QIDQ1807612zbMATH OpenOpenAlexFDO

Authors Svante Carlsson, Håkan Jonsson, Bengt J. Nilsson

Publication date 23 November 1999

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00009467

zbMATH Keywords

shortest watchman route

Mathematics Subject Classification ID

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

Recommendations

• Shortest watchman routes in simple polygons
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• Approximating a shortest watchman route
• Fast computation of shortest watchman routes in simple polygons

Cited in

(37)

• Minimum-link watchman tours
• Finding shortest safari routes in simple polygons
• Polygon exploration with time-discrete vision
• Watchman routes in the presence of a pair of convex polygons
• Approximation algorithms for the watchman route and zookeeper's problems.
• The traveling salesmanpProblem for lines in the plane
• Fast computation of shortest watchman routes in simple polygons
• An improved algorithm for computing a shortest watchman route for lines
• Routing in a polygonal terrain with the shortest beacon watchtower
• Shortest watchman tours in simple polygons under rotated monotone visibility
• On Romeo and Juliet problems: minimizing distance-to-sight
• A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
• Watchman routes for lines and line segments
• Online searching with an autonomous robot
• Online search for a hyperplane in high-dimensional Euclidean space
• Approximating a shortest watchman route
• scientific article; zbMATH DE number 426139 (Why is no real title available?)
• Gender-aware facility location in multi-gender world
• Watchman tours for polygons with holes
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• The traveling salesman problem for lines and rays in the plane
• How to Keep an Eye on Small Things
• Moving an angle around a region
• Concerning the time bounds of existing shortest watchman route algorithms
• Computing a shortest watchman path in a simple polygon in polynomial-time
• On Romeo and Juliet problems: minimizing distance-to-sight
• Theory and Applications of Models of Computation
• Finding the shortest boundary guard of a simple polygon
• Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles
• Observation routes and external watchman routes
• Approximation algorithms for the two-watchman route in a simple polygon
• Observation routes and external watchman routes
• Finding a shortest Hamiltonian path inside a simple polygon
• m-watchmen's routes in minbar and generalized minbar polygons
• Optimizing visibility-based search in polygonal domains
• Approximation algorithms for anchored multiwatchman routes
• Shortest watchman routes in simple polygons

This page was built for publication: Finding the shortest watchman route in a simple polygon

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