کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414253 680861 2015 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximating the bottleneck plane perfect matching of a point set
ترجمه فارسی عنوان
تقریبی تطبیق کامل تطابق کامل یک مجموعه نقطه
کلمات کلیدی
تطبیق هواپیما، تطبیق بطلمی نمودار هندسی، نمودار دیسک واحد الگوریتم تقریبی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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(nlog2⁡n)O(nlog2⁡n)-time. Then we extend our idea toward an O(nlog⁡n)O(nlog⁡n)-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
نویسندگان
, , , , ,