Optimum guard covers and m-watchmen routes for restricted polygons

Ntafos, Simeon (author): Computer Science Program, University of Texas at Dallas

(creator_code:org_t)

1993
1993
English.
In: International journal of computational geometry and applications. - 0218-1959. ; 3:1, s. 85-105

Related links:: https://urn.kb.se/re...; show more...; https://doi.org/10.1...; show less...

Abstract Subject headings

A watchman, in the terminology of art galleries, is a mobile guard. We consider several watchman and guard problems for different classes of polygons. We introduce the notion of vision spans along a path (route) which provide a natural connection between the Art Gallery problem, the m-watchmen problem and the watchman route problem. We prove that finding the minimum number of vision points, i.e., static guards, along a shortest watchman route is NP-hard. We provide a linear time algorithm to compute the best set of static guards in a histogram polygon. The m-watchmen problem, minimize total length of routes for m watchmen, is NP-hard for simple polygons. We give a \Theta(n 3 + n 2 m 2 )-time algorithm to compute the best set of m watchmen in a histogram. 1 Introduction The problem of placing guards in an art gallery so that every point in the gallery is visible to at least one guard has been considered by several researchers. If the gallery is represented by a polygon, ...

By the author/editor: Carlsson, Svante; Nilsson, Bengt J ...; Ntafos, Simeon

About the subject

NATURAL SCIENCES: NATURAL SCIENCES; and Mathematics; and Mathematical Ana ...

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.