Teorema da galeria de arte e variantes

Abstract

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.