کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414216 680827 2015 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bichromatic compatible matchings
ترجمه فارسی عنوان
مطابقت سازگار با رنگ آمیزی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

For a set R of n red points and a set B of n blue points, a BR-matching is a non-crossing geometric perfect matching where each segment has one endpoint in B and one in R. Two BR-matchings are compatible if their union is also non-crossing. We prove that, for any two distinct BR-matchings M   and M′M′, there exists a sequence of BR  -matchings M=M1,…,Mk=M′M=M1,…,Mk=M′ such that Mi−1Mi−1 is compatible with MiMi. This implies the connectivity of the compatible bichromatic matching graph containing one node for each BR-matching and an edge joining each pair of compatible BR-matchings, thereby answering the open problem posed by Aichholzer et al. in [1].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 48, Issue 8, September 2015, Pages 622–633
نویسندگان
, , , ,