کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868458 | 1439978 | 2018 | 27 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Point sets with many non-crossing perfect matchings
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Point sets with many non-crossing perfect matchings Point sets with many non-crossing perfect matchings](/preview/png/6868458.png)
چکیده انگلیسی
The maximum number of non-crossing straight-line perfect matchings that a set of n points in the plane can have is known to be O(10.0438n) and Ωâ(3n). The lower bound, due to GarcÃa, Noy, and Tejel (2000), is attained by the double chain, which has Î(3n/nÎ(1)) such matchings. We reprove this bound in a simplified way that uses the novel notion of down-free matchings. We then apply this approach to several other constructions. As a result, we improve the lower bound. First we show that the double zigzag chain with n points has Îâ(λn) non-crossing perfect matchings with λâ3.0532. Next we analyze further generalizations of double zigzag chains - double r-chains. The best choice of parameters leads to a construction that has Îâ(νn) matchings with νâ3.0930. The derivation of this bound requires an analysis of a coupled dynamic-programming recursion between two infinite vectors.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 68, March 2018, Pages 7-33
Journal: Computational Geometry - Volume 68, March 2018, Pages 7-33
نویسندگان
Andrei Asinowski, Günter Rote,