کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414235 | 680855 | 2014 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximating geodesic distances on 2-manifolds in R3R3
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We present an algorithm for approximating geodesic distances on 2-manifolds in R3R3. Our algorithm works on an ε-sample of the underlying manifold and computes approximate geodesic distances between all pairs of points in this sample. The approximation error is multiplicative and depends on the density of the sample. For an ε-sample S , the algorithm has a near-optimal running time of O(|S|2log|S|)O(|S|2log|S|), an optimal space requirement of O(|S|2)O(|S|2), and approximates the geodesic distances up to a factor of 1−O(ε) and (1−O(ε))−1(1−O(ε))−1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 2, Part A, February 2014, Pages 125–140
Journal: Computational Geometry - Volume 47, Issue 2, Part A, February 2014, Pages 125–140
نویسندگان
Christian Scheffer, Jan Vahrenhold,