Visibility and proximity on triangulated surfaces

dc.contributor
Universitat de Girona. Departament d'Informàtica i Matemàtica Aplicada
dc.contributor.author
Fort, Marta
dc.date.accessioned
2011-04-12T17:39:57Z
dc.date.available
2008-07-29
dc.date.issued
2008-06-05
dc.date.submitted
2008-07-29
dc.identifier.isbn
9788469159590
dc.identifier.uri
http://www.tdx.cat/TDX-0729108-122522
dc.identifier.uri
http://hdl.handle.net/10803/7890
dc.description.abstract
En aquesta tesi es solucionen problemes de visibilitat i proximitat sobre superfícies triangulades considerant elements generalitzats. Com a elements generalitzats considerem:<br/>punts, segments, poligonals i polígons. Les estrategies que proposem utilitzen algoritmes<br/>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<br/>calcular i visualitzar mapes de multi-visibilitat discrets mitjançant hardware gràfic. Com<br/>a aplicacions es resolen problemes de multi-visibilitat entre regions i es responen preguntes<br/>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.
cat
dc.description.abstract
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.
eng
dc.format.mimetype
application/pdf
dc.language.iso
eng
dc.publisher
Universitat de Girona
dc.rights.license
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.
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.subject
GPU
dc.subject
Proximidad
dc.subject
Proximitat
dc.subject
Proximity
dc.subject
Diagrama Voronoi
dc.subject
Voronoi diagram
dc.subject
Multi-visibilidad
dc.subject
Multi-visibilitat
dc.subject
Multi-visibility
dc.subject
Shortest path
dc.subject
Superficies poliédricas
dc.subject
Superfícies polièdriques
dc.subject
Polyhedral surface
dc.title
Visibility and proximity on triangulated surfaces
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.subject.udc
004
cat
dc.subject.udc
68
cat
dc.contributor.authoremail
mfort@ima.udg.edu
dc.contributor.director
Sellarès i Chiva, J. A. (Joan Antoni)
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
dc.identifier.dl
Gi. 1196-2008


Documents

tmfm.pdf

2.730Mb PDF

Aquest element apareix en la col·lecció o col·leccions següent(s)