The zookeeper route problem

DOI10.1016/0020-0255(92)90072-GzbMath0767.68090MaRDI QIDQ1193837

Wei-Pang Chin, Simeon C. Ntafos

Publication date: 27 September 1992

Published in: Information Sciences (Search for Journal in Brave)

zbMATH Keywords

path planningNP-hardpolygonszookeeper route problem

Mathematics Subject Classification ID

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

Related Items

A 2-approximation algorithm for the zookeeper's problem ⋮ Computing a shortest watchman path in a simple polygon in polynomial-time ⋮ Inspecting a Set of Strips Optimally ⋮ Shortest paths in simple polygons with polygon-meet constraints ⋮ Approximation algorithms for the watchman route and zookeeper's problems. ⋮ On finding a shortest isothetic path and its monotonicity inside a digital object ⋮ 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 ⋮ Finding shortest safari routes in simple polygons ⋮ An approximative solution to the Zookeeper's problem ⋮ Optimal placement of base stations in border surveillance using limited capacity drones ⋮ Shortest zookeeper's routes in simple polygons ⋮ An O\((n\log n)\) algorithm for the zoo-keeper's problem

Cites Work

• Unnamed Item
• Shortest watchman routes in simple polygons
• The robber route problem
• Optimum watchman routes
• The Euclidean traveling salesman problem is NP-complete
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon