Intersecting Diametral Disks of a Maximum Weight Matching

Darryl Hill

Carleton University

Let $P$ be a set of points in the plane, and consider a perfect, maximum weight matching $M$ of $P$, where weight is defined by the sum of the Euclidean distances between matched points. For points $p$ and $q$, let the diametral disk $D_{pq}$ be the disk with $p$ and $q$ on the boundary that is centered at the midpoint of $pq$. Let $D_M$ be the set of diametral disks of $M$. We show that the disks of $D_M$ have a common intersection. This was shown to be true by Huemer et al. for maximum weight matchings of red and blue points, with weight defined as the sum of the Euclidean distances squared. Our result differs in that we do not square the distances, and we permit matching any pair of points.