Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414216 | Computational Geometry | 2015 | 12 Pages |
Abstract
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].
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Greg Aloupis, Luis Barba, Stefan Langerman, Diane L. Souvaine,