Title :
Shortest m-watchmen routes for histograms: the minmax case
Author :
Nilsson, Bengt J. ; Schuierer, Sven
Author_Institution :
Dept. of Comput. Sci., Lund Univ., Sweden
Abstract :
The authors consider the problem of computing an optimum set of watchmen routes in a histogram. A watchman, in the terminology of art galleries, is a mobile guard and in this version one wants to minimize the length of the longest route in the solution. The authors give an O(n2 log n) time algorithm to compute the MinMax optimum set of m watchmen in a histogram polygon
Keywords :
computational complexity; graph theory; minimax techniques; operations research; art galleries; histogram polygon; mobile guard; watchmen routes; Art; Computer aided software engineering; Computer science; Histograms; Minimax techniques; Spirals; Terminology;
Conference_Titel :
Computing and Information, 1992. Proceedings. ICCI '92., Fourth International Conference on
Conference_Location :
Toronto, Ont.
Print_ISBN :
0-8186-2812-X
DOI :
10.1109/ICCI.1992.227712
