کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949163 | 1439987 | 2016 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper we develop a randomized divide-and-conquer algorithm to compute the order-k abstract Voronoi diagram in expected O(kn1+ε) operations. For solving small sub-instances in the divide-and-conquer process, we also give two auxiliary algorithms with expected O(k2nlogâ¡n) and O(n22α(n)logâ¡n) time, respectively, where α(â
) is the inverse of the Ackermann function. Our approach directly implies an O(kn1+ε)-time algorithm for several concrete order-k instances such as points in any convex distance, disjoint line segments or convex polygons of constant size in the Lp norms, and others. It also provides basic techniques that can enable the application of well-known random sampling techniques to the construction of Voronoi diagrams in the abstract setting and for non-point sites.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 59, December 2016, Pages 26-38
Journal: Computational Geometry - Volume 59, December 2016, Pages 26-38
نویسندگان
Cecilia Bohler, Chih-Hung Liu, Evanthia Papadopoulou, Maksym Zavershynskyi,