On Maximum-Sum Matchings of Points

EasyChair Preprint 6038

Abstract

Huemer et al. (Discrete Mathematics, 2019) proved that for any two point sets R and B 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 common point. Each pair of matched points p in R and q in B induces the disk of smallest diameter that covers p and q. Following this research line, in this article we consider the perfect matching that maximizes the total Euclidean distance. First, we prove that this new matching for R and B does not always ensure the common intersection property of the disks. Second, we extend the study of this new matching for sets of 2n uncolored points in the plane, where a matching is just a partition of the points into n pairs. As the main result, we prove that in this case all disks of the matching do have a common point.

Keyphrases: Colored points, Disks, Max-sum Euclidean matching, intersection graph, matchings

@booklet{EasyChair:6038,
  author    = {Sergey Bereg and Oscar Chacón-Rivera and David Flores-Peñaloza and Clemens Huemer and Pablo Pérez-Lantero and Carlos Seara},
  title     = {On Maximum-Sum Matchings of Points},
  howpublished = {EasyChair Preprint 6038},
  year      = {EasyChair, 2021}}