AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES

DOI10.1142/S0218195993000233zbMath0803.68137OpenAlexW2123945156MaRDI QIDQ4289632

Tomio Hirata, Yasuyoshi Inagaki, Xue-Hou Tan

Publication date: 3 May 1994

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195993000233

zbMATH Keywords

computational geometryincremental algorithmwatchman routesessential cuts

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Touring a sequence of disjoint polygons: complexity and extension, A linear-time 2-approximation algorithm for the watchman route problem for simple polygons, An Improved On-line Strategy for Exploring Unknown Polygons, Improved exploration of unknown polygons, An improved algorithm for computing a shortest watchman route for lines, Complexity of minimum corridor guarding problems, Approximation algorithms for the watchman route and zookeeper's problems., Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems, Online searching with an autonomous robot, CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES", Finding shortest safari routes in simple polygons, Polygon exploration with time-discrete vision, Fast computation of shortest watchman routes in simple polygons