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

DOI10.1016/S0925-7721(02)00092-5zbMATH Open1013.68269MaRDI QIDQ1869741FDOQ1869741

Sergei Bespamyatnikh

Publication date: 28 April 2003

Published in: Computational Geometry (Search for Journal in Brave)

Recommendations

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

zbMATH Keywords

shortest pathsfloodlight treezoo-keeper's problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Visibility and intersection problems in plane geometry
• Title not available (Why is that?)
• 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
• A new data structure for shortest path queries in a simple polygon

Cited In (6)

• A 2-approximation algorithm for the zookeeper's problem
• An approximative solution to the Zookeeper's problem
• Title not available (Why is that?)
• 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

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)