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

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
نویسندگان
,