An O(n n) algorithm for the zoo-keeper's problem

DOI10.1016/S0925-7721(02)00092-5MaRDI QIDQ1869741zbMATH OpenFDO

Authors Sergei Bespamyatnikh

Publication date 28 April 2003

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0925-7721(02)00092-5

zbMATH Keywords

floodlight treeshortest pathszoo-keeper's problem

Mathematics Subject Classification ID

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

Recommendations

• Shortest zookeeper's routes in simple polygons
• scientific article; zbMATH DE number 4066651
• scientific article; zbMATH DE number 140109
• scientific article; zbMATH DE number 1796966
• An approximative solution to the Zookeeper's problem

Cites work

• A new data structure for shortest path queries in a simple polygon
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• scientific article; zbMATH DE number 6472590 (Why is no real title available?)
• Optimal shortest path queries in a simple polygon
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• The zookeeper route problem
• Visibility and intersection problems in plane geometry

Cited in

(6)

• An approximative solution to the Zookeeper's problem
• Approximation algorithms for the watchman route and zookeeper's problems.
• Optimal placement of base stations in border surveillance using limited capacity drones
• Efficient algorithms for touring a sequence of convex polygons and related problems
• scientific article; zbMATH DE number 4066651 (Why is no real title available?)
• A 2-approximation algorithm for the zookeeper's problem

This page was built for publication: An O\((n\log n)\) algorithm for the zoo-keeper's problem

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