Autor(es):
Marques, Sylvie Lopes 
Data: 2005
Identificador Persistente: http://hdl.handle.net/10773/2884
Origem: RIA - Repositório Institucional da Universidade de Aveiro
Assunto(s): Matemática aplicada; Geometria computacional; Polígonos; Grafos
Descrição
Muitos dos problemas que surgem no quotidiano envolvem vigiar ou
iluminar regiões. Tem-se por exemplo: colocar câmaras de vigilância no
supermercado local, posicionar antenas para redes telefónicas rádio
móvel, ou mesmo iluminar a nossa sala de estar. O Problema da
Galeria de Arte [37] é um problema famoso na área da geometria
computacional que retrata formalmente este tipo de aplicações.
O Problema da Galeria de Arte para um polígono arbitrário P, tem por
objectivo encontrar um conjunto G, que contém um número mínimo de
pontos de P, de modo a que todos os pontos de P sejam visíveis de
algum ponto de G. Dois pontos dizem-se visíveis num polígono se o
segmento de recta que os une estiver totalmente contido em P.
Em 1975, Chvátal [8] mostrou que para um polígono simples com n
lados, o número mínimo de pontos de G nunca excederá 3
êënúû. Este
resultado é conhecido por Teorema da Galeria de Arte. Em 1978, Fisk
[16] propôs uma prova alternativa bastante simples. A ideia desta prova
permitiu que Avis e Toussaint [4], em 1981, desenvolvessem um
algoritmo com complexidade O(n lnn) para determinar a posição dos
3
êënúû guardas num polígono simples. No entanto, em 1986, Lee e Lin [29]
provaram que o Problema da Galeria de Arte é NP-difícil.
Desde o resultado de Chvátal, numerosas variantes do Problema da
Galeria de Arte têm vindo a ser estudadas: incluindo guardas móveis,
guardas com visibilidade ou mobilidade limitadas, iluminação de
polígonos ortogonais, entre outros.
Com o presente trabalho, pretende-se fazer uma abordagem ao estudo
do Teorema da Galeria de Arte e de algumas das suas variantes. Inicia-
-se esta dissertação com algumas noções básicas, seguidamente
introduz-se e formaliza-se o Teorema da Galeria de Arte, e finaliza-se
com o estudo de algumas das variantes supracitadas.
ABSTRACT: Many problems that arise in everyday situations involve guarding or
illuminating regions. Some examples are: placing TV-cameras in de
local supermarket, positioning radio antennas for cellular phones, or
arranging the lighting in one’s living room. The Art Gallery Problem [37]
is famous in computational geometry that formally models these types of
applications.
The Art Gallery Problem for a polygon P is to find a minimum set of
points G in P such that every point of P is visible from some point of G.
Two points in a polygon are called visible if the straight-line segment
between them lies entirely inside the polygon.
In 1975, Chvátal [8] showed that the number of points of G will never
exceed 3
êënúû for a simple polygon of n sides. This latter result is referred
to as The Art Gallery Theorem. In 1978, Fisk [16] showed an alternative
and easier proof. Avis and Toussaint [4], in 1981, mimicked Fisk’s proof
rather directly to obtain an O(n lnn) algorithm for placing 3
êënúû guards on a
simple polygon. However, the Art Gallery Problem has been shown to
be NP-Hard by Lee and Lin [29], in 1986.
Since Chvátal’s result, numerous variations on the Art Gallery Problem
have been studied, including mobile guards, guards with limited visibility
or mobility, guarding of rectilinear polygons, and others.
This work intends to be a approach to Art gallery theorem and some of it
variations. It begins with some basic notions followed by the
formalization of the Art Gallery Theorem. Finally, some of de variations
of the problem above are examined.
