Approximating generalized distance functions on weighted triangulated surfaces with applications

Full Text
Approximating-generalized.pdf embargoed access
Request a copy
When filling the form you are requesting a copy of the article, that is deposited in the institutional repository (DUGiDocs), at the autor or main autor of the article. It will be the same author who decides to give a copy of the document to the person who requests it, if it considers it appropriate. In any case, the UdG Library doesn’t take part in this process because it is not authorized to provide restricted articles.
Given P, a simple connected, possibly non-convex, 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 order-k Voronoi diagrams and for approximately solving facility location problems. Finally, we present experimental results obtained with our implementation of the provided algorithms ​
​Tots els drets reservats