کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414253 | 680861 | 2015 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximating the bottleneck plane perfect matching of a point set
ترجمه فارسی عنوان
تقریبی تطبیق کامل تطابق کامل یک مجموعه نقطه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تطبیق هواپیما، تطبیق بطلمی نمودار هندسی، نمودار دیسک واحد الگوریتم تقریبی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A bottleneck plane perfect matching of a set of n points in R2R2 is defined to be a perfect non-crossing matching that minimizes the length of the longest edge; the length of this longest edge is known as bottleneck . The problem of computing a bottleneck plane perfect matching has been proved to be NP-hard. We present an algorithm that computes a bottleneck plane matching of size at least n5 in O(nlog2n)O(nlog2n)-time. Then we extend our idea toward an O(nlogn)O(nlogn)-time approximation algorithm which computes a plane matching of size at least 2n5 whose edges have length at most 2+3 times the bottleneck.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 48, Issue 9, October 2015, Pages 718–731
Journal: Computational Geometry - Volume 48, Issue 9, October 2015, Pages 718–731
نویسندگان
A. Karim Abu-Affash, Ahmad Biniaz, Paz Carmi, Anil Maheshwari, Michiel Smid,