<p>Huemer et al. (Discrete Math, 2019) proved that for any two finite point sets <i>R</i> and <i>B</i> in the plane with <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(|R| = |B|\)</EquationSource> </InlineEquation>, the perfect matching that matches points of <i>R</i> with points of <i>B</i>, and maximizes the total <i>squared</i> 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..</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On maximum-sum matchings of bichromatic points

  • Oscar Chacón-Rivera,
  • Pablo Pérez-Lantero

摘要

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..