Piercing Diametral Disks Induced by Edges of Maximum Spanning Tree
share
Let P be a set of points in the plane and let T be a maximum-weight spanning tree of P. For an edge (p,q), let D_pq be the diametral disk induced by (p,q), i.e., the disk having the segment pq as its diameter. Let D_T be the set of the diametral disks induced by the edges of T. In this paper, we show that one point is sufficient to pierce all the disks in D_T, thus, the set D_T is Helly. Actually, we show that the center of the smallest enclosing circle of P is contained in all the disks of D_T, and thus the piercing point can be computed in linear time.
READ FULL TEXT