Sökning: onr:"swepub:oai:DiVA.org:ltu-3680" >
Optimum guard cover...
Optimum guard covers and m-watchmen routes for restricted polygons
-
- Carlsson, Svante (författare)
- Luleå tekniska universitet
-
- Nilsson, Bengt J. (författare)
- Department of Computer Science, Lund University
-
- Ntafos, Simeon (författare)
- Computer Science Program, University of Texas at Dallas
-
(creator_code:org_t)
- 1993
- 1993
- Engelska.
-
Ingår i: International journal of computational geometry and applications. - 0218-1959. ; 3:1, s. 85-105
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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, ...
Ämnesord
- NATURVETENSKAP -- Matematik -- Matematisk analys (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Mathematical Analysis (hsv//eng)
Nyckelord
- Matematik
- Mathematics
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas