Processing math: 100%
In­ter­sect­ing Di­ame­tral Disks of a Max­i­mum Weight Match­ing
Dar­ryl Hill
Car­leton Uni­ver­sity

Let P be a set of points in the plane, and con­sider a per­fect, max­i­mum weight match­ing M of P, where weight is de­fined by the sum of the Eu­clid­ean dis­tances be­tween matched points. For points p and q, let the di­ame­tral disk D_{pq} be the disk with p and q on the bound­ary that is cen­tered at the mid­point of pq. Let D_M be the set of di­ame­tral disks of M. We show that the disks of D_M have a com­mon in­ter­sec­tion. This was shown to be true by Hue­mer et al. for max­i­mum weight match­ings of red and blue points, with weight de­fined as the sum of the Eu­clid­ean dis­tances squared. Our re­sult dif­fers in that we do not square the dis­tances, and we per­mit match­ing any pair of points.