کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414751 | 681020 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bottleneck non-crossing matching in the plane
ترجمه فارسی عنوان
تطبیق تطابق غیرقابل عبور در هواپیما
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let P be a set of 2n points in the plane, and let MCMC (resp., MNCMNC) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of P . We study the problem of computing MNCMNC. We first prove that the problem is NP-hard and does not admit a PTAS. Then, we present an O(n1.5log0.5n)-time algorithm that computes a non-crossing matching M of P , such that bn(M)⩽210⋅bn(MNC), where bn(M)bn(M) is the length of a longest edge in M . An interesting implication of our construction is that bn(MNC)/bn(MC)⩽210. Finally, we show that when the points of P are in convex position, one can compute MNCMNC in O(n3)O(n3) time, improving a result in [7].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 3, Part A, April 2014, Pages 447–457
Journal: Computational Geometry - Volume 47, Issue 3, Part A, April 2014, Pages 447–457
نویسندگان
A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz, Yohai Trabelsi,