An O(nlogn) Algorithm for the Zoo-keeper's ProblemAbstract: 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."} @article{b-azp-02 , 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 } |