Sobre iluminação de polígonos com focos ou reflectores em vértices

Abstract

O Problema da Galeria de Arte e as suas variantes têm sido intensivamente estudados desde os anos 70, mantendo-se vários problemas em aberto. Um dos problemas da classe de Problemas da Galeria de Arte é o da colocação de focos em vértices dum polígono de forma que o iluminem completamente e o seu número seja mínimo. Este é um problema NP-difícil. Nesta dissertação, abordamos algumas variantes deste problema, nomeadamente para polígonos ortogonais (com e sem buracos) e focos com amplitude de iluminação 2π, π e π/2. Apresentamos um método que permite determinar o valor óptimo de focos por aproximações sucessivas e que segue a estratégia adoptada em [Tomás e al. 2004]. As aproximações são obtidas por resolução de sub-problemas de cobertura mínima, sendo melhoradas através do refinamento da partição inicial do polígono. Descrevemos ainda a aplicação desenvolvida para avaliação experimental do método nas diferentes variantes do Problema da Galeria de Arte mencionadas. Esta aplicação permite ainda escolher a partição inicial. Nessa avaliação experimental foram usadas amostras constituídas por polígonos ortogonais aleatórios com n vértices, representáveis numa grelha regular com exactamente uma aresta em cada linha da grelha. Para focos de amplitude 2π, concluímos que o número de guardas mínimo era n/6. Este valor é inferior ao valor teórico ⎣n/4⎦, suficiente para guardar qualquer polígono ortogonal e ocasionalmente necessário. Para polígonos com dois buracos rectangulares, gerados a partir de polígonos da amostra referida, verificámos que o número de guardas mínimo era (n+h)/6. Neste caso, a conjectura é que bastam sempre ⎣(n+h)/4⎦ guardas para vigiar um polígono ortogonal genérico com h buracos (sendo ocasionalmente necessários). Para reflectores, é habitual impor que seja colocado, no máximo, um reflector por vértice. Os nossos resultados não verificam necessariamente esta condição. As funções que interpolam os resultados experimentais que obtivemos para π-reflectores e π/2-reflectores para polígonos ortogonais simples são respectivamente fπ(n) = (11n-30)/50 e fπ/2(n) = (23n-60)/100. Para polígonos com dois buracos rectangulares, as funções que interpolam os valores obtidos fπ(n) = (9n-52)/40 e fπ/2(n) = (17n+4)/80.

ABSTRACT: The Art Gallery Problem and its variants have been extensively studied since the seventies, several problems remaining open. In this thesis we address the problem of placing a minimum number of lights (guards) on the vertices of a polygon so that the whole polygon is illuminated (guarded). It is known that this is an NP-hard problem. We focus on orthogonal polygons (with and without holes) and lights with illumination range limited to 2π, π and π/2. We present an algorithm to compute the minimum number of lights by successive approximations, that follows the strategy proposed in [Tomás et al. 2004]. Each approximation is obtained by solving a minimum set covering problem for a given partition. Better approximations are achieved by refining the initial partition of the polygon. We describe the implementation we developed to experimentally evaluate this method for the different variants. This application allows the choice of different initial partitions. For that evaluation, we used random n-vertex orthogonal polygons that can be represented on a regular grid with exactly one edge in each line of the grid. For lights with amplitude 2π, we concluded that the minimum number of guards for random polygons is n/6. This value is smaller than the theoretical value ⎣n/4⎦, that is always sufficient and sometimes necessary to guard an n-vertex orthogonal polygon. Random polygons with two rectangular holes were generated using the samples mentioned earlier. For these random samples, we verified that the minimum number of guards was (n+h)/6. In this case, the existing conjecture was that ⎣(n+h)/4⎦ guards are always sufficient and occasionally necessary to guard an n-vertex orthogonal polygon with h holes. For reflex vertices, we have not imposed any condition on the number of guards per vertex, although it is usually required that this number does not exceed one. The experimental results indicate that for π-reflectors and π/2- reflectors on orthogonal polygons the minimum number of guards is interpolated by fπ(n) = (11n-30)/50 and fπ/2(n) = (23n-60)/100. For polygons with two rectangular holes, these corresponding functions are fπ(n) = (9n-52)/40 and fπ/2(n) = (17n+4)/80.