کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414751 681020 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bottleneck non-crossing matching in the plane
ترجمه فارسی عنوان
تطبیق تطابق غیرقابل عبور در هواپیما
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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