Item
Fort, Marta
SellarÃ¨s i Chiva, Joan Antoni 

2012  
Given P, a simple connected, possibly nonconvex, polyhedral surface composed of positively weighted triangular faces, we consider paths from generalized sources (points, segments, polygonal chains or polygonal regions) to points on P that stay on P and avoid obstacles (segments, polygonal chains or polygonal regions). The distance function defined by a generalized source is a function that assigns to each point of P the cost of the shortest path from the source to the point. In this paper we present an algorithm for computing approximate generalized distance functions. We also provide an algorithm that computes a discrete representation of the approximate distance function and, as applications, algorithms for computing discrete orderk Voronoi diagrams and for approximately solving facility location problems. Finally, we present experimental results obtained with our implementation of the provided algorithms This work was partially supported by the Spanish Ministerio de Ciencia e Innovacion under grant TIN201020590C0202 

application/pdf  
03770427  
http://hdl.handle.net/10256/11987  
eng  
Elsevier  
MICINN/PN 20112013/TIN201020590C0202 ReproducciÃ³ digital del document publicat a: http://dx.doi.org/10.1016/j.cam.2012.03.028 Articles publicats (DIMA) 

Â© Journal of Computational and Applied Mathematics, 2012, vol. 236, nÃºm. 14, p. 34613477  
Tots els drets reservats  
PolÃgons
Polygons Algorismes computacionals Computer algorithms 

Approximating generalized distance functions on weighted triangulated surfaces with applications  
info:eurepo/semantics/article  
DUGiDocs 