An approximative solution to the Zookeeper's problem

DOI10.1016/S0020-0190(03)00348-XzbMath1183.68663MaRDI QIDQ1014446

Håkan Jonsson

Publication date: 28 April 2009

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

zbMATH Keywords

shortest pathcomputational geometryZookeeper's problem

Mathematics Subject Classification ID

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

Related Items

A 2-approximation algorithm for the zookeeper's problem ⋮ Approximation algorithms for the watchman route and zookeeper's problems. ⋮ A sequential convex programming algorithm for minimizing a sum of Euclidean norms with non-convex constraints

Cites Work

• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Triangulating a simple polygon in linear time
• The zookeeper route problem
• Shortest zookeeper's routes in simple polygons
• An O\((n\log n)\) algorithm for the zoo-keeper's problem
• Unnamed Item
• Unnamed Item