کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949141 | 1439986 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Dynamic data structures for approximate Hausdorff distance in the word RAM
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We give a fully dynamic data structure for maintaining an approximation of the Hausdorff distance between two point sets in a constant dimension d, a standard problem in computational geometry. Our solution has an approximation factor of 1+ε for any constant ε>0 and expected update time O(logâ¡Ulogâ¡logâ¡n), where U is the universe size, and n is the number of the points. The result of the paper greatly improves over the previous exact method, which required O(n5/6polylogn) time and worked only in a semi-online setting. The model of computation is the word RAM model.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 60, January 2017, Pages 37-44
Journal: Computational Geometry - Volume 60, January 2017, Pages 37-44
نویسندگان
Timothy M. Chan, Dimitrios Skrepetos,