Geometric optimization on visibility problems: metaheuristic and exact solutions

Abstract

Os problemas de visibilidade têm diversas aplicações a situações reais. Entre os mais conhecidos, e exaustivamente estudados, estão os que envolvem os conceitos de vigilância e ocultação em estruturas geométricas (problemas de vigilância e ocultação). Neste trabalho são estudados problemas de visibilidade em estruturas geométricas conhecidas como polígonos, uma vez que estes podem representar, de forma apropriada, muitos dos objectos reais e são de fácil manipulação computacional. O objectivo dos problemas de vigilância é a determinação do número mínimo de posições para a colocação de dispositivos num dado polígono, de modo a que estes dispositivos consigam “ver” a totalidade do polígono. Por outro lado, o objectivo dos problemas de ocultação é a determinação do número máximo de posições num dado polígono, de modo a que quaisquer duas posições não se consigam “ver”. Infelizmente, a maior parte dos problemas de visibilidade em polígonos são NP-difíceis, o que dá origem a duas linhas de investigação: o desenvolvimento de algoritmos que estabelecem soluções aproximadas e a determinação de soluções exactas para classes especiais de polígonos. Atendendo a estas duas linhas de investigação, o trabalho é dividido em duas partes. Na primeira parte são propostos algoritmos aproximados, baseados essencialmente em metaheurísticas e metaheurísticas híbridas, para resolver alguns problemas de visibilidade, tanto em polígonos arbitrários como ortogonais. Os problemas estudados são os seguintes: “Maximum Hidden Vertex Set problem”, “Minimum Vertex Guard Set problem”, “Minimum Vertex Floodlight Set problem” e “Minimum Vertex k-Modem Set problem”. São também desenvolvidos métodos que permitem determinar a razão de aproximação dos algoritmos propostos. Para cada problema são implementados os algoritmos apresentados e é realizado um estudo estatístico para estabelecer qual o algoritmo que obtém as melhores soluções num tempo razoável. Este estudo permite concluir que as metaheurísticas híbridas são, em geral, as melhores estratégias para resolver os problemas de visibilidade estudados. Na segunda parte desta dissertação são abordados os problemas “Minimum Vertex Guard Set”, “Maximum Hidden Set” e “Maximum Hidden Vertex Set”, onde são identificadas e estudadas algumas classes de polígonos para as quais são determinadas soluções exactas e/ou limites combinatórios.

Visibility problems have several applications to real-life problems. Among the most distinguished and exhaustively studied visibility problems are the ones involving concepts of guarding and hiding on geometrical structures (guarding and hiding problems). This work deals with visibility problems on geometrical structures known as polygons, since polygons are appropriate representations of many real-world objects and are easily handled by computers. The objective of the guarding problems studied in this thesis is to find a minimum number of device positions on a given polygon such that these devices collectively ''see'' the whole polygon. On the other hand, the goal of the hiding problems is to find a maximum number of positions on a given polygon such that no two of these positions can “see" each other. Unfortunately, most of the visibility problems on polygons are NP-hard, which opens two lines of investigation: the development of algorithms that establish approximate solutions and the determination of exact solutions on special classes of polygons. Accordingly, this work is divided in two parts where these two lines of investigation are considered. The first part of this thesis proposes approximation algorithms, mainly based on metaheuristics and hybrid metaheuristics, to tackle some visibility problems on arbitrary and orthogonal polygons. The addressed problems are the Maximum Hidden Vertex Set problem, the Minimum Vertex Guard Set problem, the Minimum Vertex Floodlight Set problem and the Minimum Vertex k-Modem Set problem. Methods that allow the determination of the performance ratio of the developed algorithms are also proposed. For each problem, the proposed algorithms are implemented and a statistical study is performed to determine which of the developed methods obtains the best solution in a reasonable amount of time. This study allows to conclude that, in general, the hybrid metaheuristics are the best approach to solve the studied visibility problems. The second part of this dissertation addresses the Minimum Vertex Guard Set problem, the Maximum Hidden Set problem and the Maximum Hidden Vertex Set problem, where some classes of polygons are identified and studied and for which are determined exact solutions and/or combinatorial bounds.