کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4632902 | 1340657 | 2009 | 16 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Computing generalized higher-order Voronoi diagrams on triangulated surfaces Computing generalized higher-order Voronoi diagrams on triangulated surfaces](/preview/png/4632902.png)
We present an algorithm for computing exact shortest paths, and consequently distance functions, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex triangulated polyhedral surface. The algorithm is generalized to the case when a set of generalized sites is considered, providing their distance field that implicitly represents the Voronoi diagram of the sites. Next, we present an algorithm to compute a discrete representation of the distance function and the distance field. Then, by using the discrete distance field, we obtain the Voronoi diagram of a set of generalized sites (points, segments, polygonal chains or polygons) and visualize it on the triangulated surface. We also provide algorithms that, by using the discrete distance functions, provide the closest, furthest and k-order Voronoi diagrams and an approximate 1-Center and 1-Median.
Journal: Applied Mathematics and Computation - Volume 215, Issue 1, 1 September 2009, Pages 235–250