کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414216 | 680827 | 2015 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bichromatic compatible matchings
ترجمه فارسی عنوان
مطابقت سازگار با رنگ آمیزی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Computational Geometry - Volume 48, Issue 8, September 2015, Pages 622–633
نویسندگان
Greg Aloupis, Luis Barba, Stefan Langerman, Diane L. Souvaine,