کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4639689 | 1341245 | 2012 | 17 صفحه PDF | دانلود رایگان |
Given PP, 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 PP that stay on PP 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 PP 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-kk Voronoi diagrams and for approximately solving facility location problems. Finally, we present experimental results obtained with our implementation of the provided algorithms.
Journal: Journal of Computational and Applied Mathematics - Volume 236, Issue 14, August 2012, Pages 3461–3477