Author(s):
Gonçalves, Ana Rosa Marques 
Date: 2007
Persistent ID: http://hdl.handle.net/10773/2897
Origin: RIA - Repositório Institucional da Universidade de Aveiro
Subject(s): Matemática; Geometria computacional; Polígonos
Description
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. Mestrado em Matemática
Document Type
Master Thesis
Language
Portuguese
Advisor(s)
Bajuelos Dominguez, António Leslie; Tomás, Ana Paula
