Visibility and proximity on triangulated surfaces

Abstract

En aquesta tesi es solucionen problemes de visibilitat i proximitat sobre superfícies triangulades considerant elements generalitzats. Com a elements generalitzats considerem: punts, segments, poligonals i polígons. Les estrategies que proposem utilitzen algoritmes de geometria computacional i hardware gràfic. Comencem tractant els problemes de visibilitat sobre models de terrenys triangulats considerant un conjunt d'elements de visió generalitzats. Es presenten dos mètodes per obtenir, de forma aproximada, mapes de multi-visibilitat. Un mapa de multi-visibilitat és la subdivisió del domini del terreny que codifica la visibilitat d'acord amb diferents criteris. El primer mètode, de difícil implementació, utilitza informació de visibilitat exacte per reconstruir de forma aproximada el mapa de multi-visibilitat. El segon, que va acompanyat de resultats d'implementació, obté informació de visibilitat aproximada per calcular i visualitzar mapes de multi-visibilitat discrets mitjançant hardware gràfic. Com a aplicacions es resolen problemes de multi-visibilitat entre regions i es responen preguntes sobre la multi-visibilitat d'un punt o d'una regió. A continuació tractem els problemes de proximitat sobre superfícies polièdriques triangulades considerant seus generalitzades. Es presenten dos mètodes, amb resultats d'implementació, per calcular distàncies des de seus generalitzades sobre superfícies polièdriques on hi poden haver obstacles generalitzats. El primer mètode calcula, de forma exacte, les distàncies definides pels camins més curts des de les seus als punts del poliedre. El segon mètode calcula, de forma aproximada, distàncies considerant els camins més curts sobre superfícies polièdriques amb pesos. Com a aplicacions, es calculen diagrames de Voronoi d'ordre k, i es resolen, de forma aproximada, alguns problemes de localització de serveis. També es proporciona un estudi teòric sobre la complexitat dels diagrames de Voronoi d'ordre k d'un conjunt de seus generalitzades en un poliedre sense pesos.

In this thesis, we solve visibility and proximity problems on triangulated surfaces concerning generalized elements. As generalized elements, we consider: points, segments, polygonal chains and polygonal regions. The proposed strategies use algorithms of Computational Geometry and Graphics Hardware. We start by studying multi-visibility problems on triangulated terrain models concerning a set of generalized view elements. We present two methods to obtain approximate multi-visibility maps. A multi-visibility map is a subdivision of the terrain domain encoding visibility according to different criteria. The first method, of complex implementation, uses exactly computed visibility information to approximately reconstruct the unknown multi-visibility map. The second, from which implementation results are provided, uses approximate visibility information to compute and visualize discrete multi-visibility maps by exploiting graphics hardware capabilities. As applications, we compute multi-visibility maps, solve inter-region multi-visibility problems and approximately answer point and polygonal region multi-visibility queries. Next, we tackle proximity problems on triangulated polyhedral surfaces, where generalized obstacles are allowed, considering generalized sources. We present two methods, with implementation results, to compute distances on polyhedral surfaces from a generalized source. The first method computes exact shortest path distances from generalized sources. The second provides approximate weighted shortest path distances from generalized sites on weighted polyhedral surfaces. Both methods are posteriorly extended to handle the multiple-site problem where the corresponding distance field is obtained. As applications, we compute discrete order-k Voronoi diagrams and approximately solve some facility location problems. We also provide a theoretical study on the order-k Voronoi diagram complexity of a set of generalized sources for the non-weighted case.