Finding shortest safari routes in simple polygons

DOI10.1016/S0020-0190(03)00284-9zbMath1161.68700OpenAlexW2057025928MaRDI QIDQ1014417

Tomio Hirata, Xue-Hou Tan

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(03)00284-9

zbMATH Keywords

computational geometryadjustmentssafari routesZookeeper's routes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

A 2-approximation algorithm for the zookeeper's problem ⋮ Shortest paths in simple polygons with polygon-meet constraints ⋮ Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems ⋮ On finding a shortest isothetic path and its monotonicity inside a digital object ⋮ EXISTENCE AND COMPUTATION OF TOURS THROUGH IMPRECISE POINTS ⋮ Query-point visibility constrained shortest paths in simple polygons ⋮ A sequential convex programming algorithm for minimizing a sum of Euclidean norms with non-convex constraints ⋮ Optimal placement of base stations in border surveillance using limited capacity drones ⋮ How to Keep an Eye on Small Things

Cites Work

• Shortest watchman routes in simple polygons
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Optimum watchman routes
• Triangulating a simple polygon in linear time
• Watchman routes under limited visibility
• The zookeeper route problem
• Fast computation of shortest watchman routes in simple polygons
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
• Concerning the time bounds of existing shortest watchman route algorithms
• Unnamed Item