AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES

DOI10.1142/S0218195993000233zbMATH Open0803.68137OpenAlexW2123945156MaRDI QIDQ4289632FDOQ4289632

Authors: Tomio Hirata, Yasuyoshi Inagaki, Xuehou 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

Recommendations

• Finding the shortest watchman route in a simple polygon
• Shortest watchman routes in simple polygons
• Fast computation of shortest watchman routes in simple polygons
• Approximating a shortest watchman route
• Concerning the time bounds of existing shortest watchman route algorithms

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)

Cited In (23)

• An improved algorithm for computing a shortest watchman route for lines
• Touring a sequence of disjoint polygons: complexity and extension
• Optimum watchman routes
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
• Computational Science and Its Applications – ICCSA 2004
• Concerning the time bounds of existing shortest watchman route algorithms
• Computing a shortest watchman path in a simple polygon in polynomial-time
• Fast computation of shortest watchman routes in simple polygons
• Shortest watchman routes in simple polygons
• Routing in a polygonal terrain with the shortest beacon watchtower
• Approximation algorithms for the two-watchman route in a simple polygon
• Complexity of minimum corridor guarding problems
• Online searching with an autonomous robot
• Approximating a shortest watchman route
• Polygon exploration with time-discrete vision
• Efficient algorithms for touring a sequence of convex polygons and related problems
• Approximation algorithms for the watchman route and zookeeper's problems.
• GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST
• An improved on-line strategy for exploring unknown polygons
• A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
• Finding the shortest boundary guard of a simple polygon
• Finding shortest safari routes in simple polygons
• Improved exploration of unknown polygons

This page was built for publication: AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES

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