2019/02/22 by Huemer, Clemens, Pérez-Lantero, Pablo, Seara, Carlos +1 · 1 citation
#Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1902.08427
We consider matchings with diametral disks between two sets of points R and B. More precisely, for each pair of matched points p in R and q in B, we consider the disk through p and q with the smallest diameter. We prove that for any R and B such that |R|=|B|, there exists a perfect matching such that the diametral disks of the matched point pairs have a common intersection. In fact, our result is stronger, and shows that a maximum weight perfect matching has this property.