Abstract | ||
---|---|---|
In this paper we consider the problem of computing an optimum set of watchmen routesin a histogram. A watchman, in the terminology of art galleries, is a mobile guard and inthis version we want to minimize the length of the longest route in the solution. We givean O(n2log n) time algorithm to compute the MinMax optimum set of m watchmen in ahistogram polygon and we extend the algorithm to solve the Weighted MinMax problemunder the same time bound.1 IntroductionThe problem of... |
Year | DOI | Venue |
---|---|---|
1992 | 10.1109/ICCI.1992.227712 | Toronto, Ont. |
Keywords | Field | DocType |
computational complexity,graph theory,minimax techniques,operations research,art galleries,histogram polygon,mobile guard,watchmen routes | Graph theory,Histogram,Binary logarithm,Combinatorics,Minimax,Polygon,Terminology,Computer science,Guard (information security),Computational complexity theory | Conference |
ISBN | Citations | PageRank |
0-8186-2812-X | 1 | 0.46 |
References | Authors | |
6 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bengt J. Nilsson | 1 | 210 | 24.43 |
Sven Schuierer | 2 | 308 | 29.35 |