Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Cover of the book
Tytuł książki

Cooperative guards in art galleries

Seria
Rozprawy Matematyczne tom/nr w serii: 450 wydano: 2007
Zawartość
Warianty tytułu
Abstrakty
EN
The art gallery problem was originally posed by Victor Klee in 1973 as the question of determining the minimum number of guards sufficient to see every point of the interior of an n-vertex simple polygon. The guard is assumed to be a stationary point which can see any other point that can be connected to it by a line segment within the art gallery. The first result is due to Chvátal (1975), who proved that ⌊n/3⌋ guards are occasionally necessary and always sufficient to cover a polygon with n vertices. Since then many different variations of this problem have arisen, and in this dissertation, we investigate the cooperative guards problem posed by Liaw, Huang and Lee in 1993. In general, two variants of the cooperation are distinguished: a guard set is said to be cooperative provided that for any guard, if something goes wrong with him, all the others can be informed (by using the line-of-sight communication only), and k-guarded if each guard is seen by at least k of its colleagues. We present tight bounds for various classes of galleries (arbitrary, orthogonal, monotone, spiral, star-shaped, with holes) as well as we discuss the complexity of the problem of determining the minimum number of cooperative (resp. k-guarded) guards sufficient to cover an art gallery. Finally, we investigate the cooperative guards problem in fortresses and grids.
Słowa kluczowe
Tematy
Miejsce publikacji
Warszawa
Copyright
Seria
Rozprawy Matematyczne tom/nr w serii: 450
Liczba stron
132
Liczba rozdzia³ów
Opis fizyczny
Daty
wydano
2007
Twórcy
  • Institute of Computer Science, University of Gdańsk, Wita Stwosza 57, 80-952 Gdańsk, Poland
Bibliografia
Języki publikacji
EN
Uwagi
Identyfikator YADDA
bwmeta1.element.bwnjournal-rm-doi-10_4064-dm450-0-1
Identyfikatory
DOI
10.4064/dm450-0-1
Kolekcja
DML-PL
Zawartość książki

rozwiń roczniki

JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.