An O(nlogn) Algorithm for the Zoo-keeper's Problem

Abstract: We consider the Zoo-keeper's problem which asks for the shortest closed zoo-keeper's path starting at a given point of the zoo and touching all the cages in the zoo.

We present an O(nlgn) algorithm for the zoo-keeper's problem where n is the input size. The algorithm is based on a new data structure called the floodlight tree. We extend the approach to answer zoo-keeper's queries where one wants to find a zoo-keeper's path with a fixed start point, but an arbitrary final point. We show that zoo-keeper's queries can be answered in optimal time O(lgn+K) where K is the output size.

pdf file submitted to a journal.

@string{CGTA    = "Comput. Geom. Theory Appl."} 

, author = "S. Bespamyatnikh"
, title = "An $O(n\log n)$ algorithm for the {Z}oo-keeper's problem"
, journal = CGTA
, volume = 24
, number = 2
, pages = "63-74"
, year = 2002