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 algoritmesde 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 percalcular i visualitzar mapes de multi-visibilitat discrets mitjançant hardware gràfic. Coma aplicacions es resolen problemes de multi-visibilitat entre regions i es responen preguntessobre 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.
| Identifer | oai:union.ndltd.org:TDX_UDG/oai:www.tdx.cat:10803/7890 |
| Date | 05 June 2008 |
| Creators | Fort, Marta |
| Contributors | Sellarès i Chiva, J. A. (Joan Antoni), Universitat de Girona. Departament d'Informàtica i Matemàtica Aplicada |
| Publisher | Universitat de Girona |
| Source Sets | Universitat de Girona |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs., info:eu-repo/semantics/openAccess |
Page generated in 0.003 seconds