Aichholzer, Oswin (A-TGRZ-ISF); Bereg, Sergey [Bereg, Sergey N.](1-TXD-C); Dumitrescu, Adrian (1-WIM-C); Garcıa, Alfredo [Garcıa Olaverri, Alfredo](E-ZRGZ-SM);... Academic Article uri icon


  • Summary:“This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non- crossing. Our first result states that for any two perfect matchings M and M∨ of the same set of n points, for some k∈ 0 (log n), there is a sequence of perfect matchings M= M0, M1,..., Mk= M∨, such that each Mi is compatible with Mi+ 1. This improves the previous best bound of k≤ n− 2. We then study the conjecture: every perfect matching with an even number of …

publication date

  • January 1, 2009