کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414302 | 680884 | 2014 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Overlap of convex polytopes under rigid motion
ترجمه فارسی عنوان
همپوشانی چند جمله ای محدب تحت حرکت سفت و سخت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
چند ضلعی محدب تطابق شکل، حرکت سخت همپوشانی الگوریتم تقریبی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We present an algorithm to compute a rigid motion that approximately maximizes the volume of the intersection of two convex polytopes P1P1 and P2P2 in R3R3. For all ε∈(0,1/2]ε∈(0,1/2] and for all n⩾1/εn⩾1/ε, our algorithm runs in O(ε−3nlog3.5n) time with probability 1−n−O(1)1−n−O(1). The volume of the intersection guaranteed by the output rigid motion is a (1−ε)(1−ε)-approximation of the optimum, provided that the optimum is at least λ⋅max{|P1|,|P2|}λ⋅max{|P1|,|P2|} for some given constant λ∈(0,1]λ∈(0,1].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 1, January 2014, Pages 15–24
Journal: Computational Geometry - Volume 47, Issue 1, January 2014, Pages 15–24
نویسندگان
Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, Juyoung Yon,