کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414321 | 680888 | 2012 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An improved algorithm for Kleeʼs measure problem on fat boxes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The measure problem of Klee asks for the volume of the union of n axis-parallel boxes in a fixed dimension d . We give an O(n(d+2)/3)O(n(d+2)/3) time algorithm for the special case of all boxes being cubes or, more generally, fat boxes. Previously, the fastest run-time was nd/22O(log⁎n), achieved by the general case algorithm of Chan [SoCG 2008]. For the general problem our run-time would imply a breakthrough for the k-clique problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 45, Issues 5–6, July 2012, Pages 225–233
Journal: Computational Geometry - Volume 45, Issues 5–6, July 2012, Pages 225–233
نویسندگان
Karl Bringmann,