A classic problem Computational Geometry is finding all euclidean shortest paths in a simple polygon from a given source vertex to every other vertex in the boundary. In this text, we give a detailed description of the Visibility Graph and Shortest Path Tree structures that solve this problem and also present the Shortest Path Map structure that extends the solution to shortest paths to every point inside the polygon. / Um problema clássico em Geometria Computacional é: encontrar todos os caminhos mínimos euclidianos dentro de um polígono simples a partir de um dado vértice fonte para todos os outros vértices da borda. Neste texto, apresentamos detalhadamente as estruturas de Grafo de Visibilidade e Árvore de Caminhos Mínimos que resolvem este problema e descrevemos também a estrutura Mapa de Caminhos Mínimos que estende a solução para todos os pontos contidos dentro do polígono.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-22082019-134801 |
| Date | 11 July 2019 |
| Creators | Rodrigues, Mateus Barros |
| Contributors | Ferreira, Carlos Eduardo |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | English |
| Detected Language | Portuguese |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0023 seconds