کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
415459 681211 2013 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Maximum overlap of convex polytopes under translation
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Maximum overlap of convex polytopes under translation
چکیده انگلیسی

We study the problem of maximizing the overlap of two convex polytopes under translation in RdRd for some constant d⩾3d⩾3. Let n   be the number of bounding hyperplanes of the polytopes. We present an algorithm that, for any ε>0ε>0, finds an overlap at least the optimum minus ε   and reports the translation realizing it. The running time is O(n⌊d/2⌋+1logdn) with probability at least 1−n−O(1)1−n−O(1), which can be improved to O(nlog3.5n) in R3R3. The time complexity analysis depends on a bounded incidence condition that we enforce with probability one by randomly perturbing the input polytopes. The perturbation causes an additive error ε, which can be made arbitrarily small by decreasing the perturbation magnitude. Our algorithm in fact computes the maximum overlap of the perturbed polytopes. The running time bounds, the probability bound, and the big-O constants in these bounds are independent of ε.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 5, July 2013, Pages 552–565
نویسندگان
, , ,