Finding the shortest watchman route in a simple polygon

DOI10.1007/PL00009467zbMath0939.68136OpenAlexW1986642089MaRDI QIDQ1807612

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

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

Related Items (21)

Unnamed Item ⋮ 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 ⋮ A linear-time 2-approximation algorithm for the watchman route problem for simple polygons ⋮ Online search for a hyperplane in high-dimensional Euclidean space ⋮ Watchman tours for polygons with holes ⋮ Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles ⋮ Observation routes and external watchman routes ⋮ Watchman routes for lines and line segments ⋮ Approximation algorithms for the watchman route and zookeeper's problems. ⋮ Finding a shortest Hamiltonian path inside a simple polygon ⋮ THE TRAVELING SALESMAN PROBLEM FOR LINES AND RAYS IN THE PLANE ⋮ Online searching with an autonomous robot ⋮ Minimum-link watchman tours ⋮ Polygon exploration with time-discrete vision ⋮ On Romeo and Juliet problems: minimizing distance-to-sight ⋮ On Romeo and Juliet Problems: Minimizing Distance-to-Sight. ⋮ How to Keep an Eye on Small Things ⋮ The traveling salesmanpProblem for lines in the plane ⋮ Fast computation of shortest watchman routes in simple polygons

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