2024/03/13 by Oscar Chacón-Rivera, Chacón-Rivera, Oscar, Pablo Pérez-Lantero +1
Computer Science · Social Sciences · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Geographic Information Systems Studies
paper · pdf · doi:10.48550/arxiv.2403.08977
openalex publication_date 2024/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Huemer et al. (Discrete Math, 2019) proved that for any two finite point sets R and B in the plane with |R| = |B|, the perfect matching that matches points of R with points of B, and maximizes the total squared Euclidean distance of the matched pairs, has the property that all the disks induced by the matching have a nonempty common intersection. A pair of matched points induces the disk that has the segment connecting the points as diameter. In this note, we characterize these maximum-sum matchings for some family of continuous (semi-)metrics, focusing on both the Euclidean distance and squared Euclidean distance. Using this characterization, we give a different but simpler proof for the common intersection property proved by Huemer et al..