id:"swepub:oai:DiVA.org:ltu-3680"
Sökning: id:"swepub:oai:DiVA.org:ltu-3680" > Optimum guard cover...
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
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
- Tidskriftsartikel (refereegranskat)
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
- International journal of computational geometry and applications (Sök värdpublikationen i LIBRIS)
Till lärosätets databas
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
Hitta mer i SwePub
- Av författaren/redakt...
- Carlsson, Svante
- Nilsson, Bengt J ...
- Ntafos, Simeon
- Om ämnet
-
- NATURVETENSKAP
- NATURVETENSKAP
- och Matematik
- och Matematisk analy ...
- Artiklar i publikationen
- International jo ...
- Av lärosätet
- Luleå tekniska universitet
Sök utanför SwePub
- Sök vidare i:
- Google Book Search
- Google Scholar
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.
- Copyright © LIBRIS - Nationella bibliotekssystem
- LIBRIS.kb.se
