TY - JOUR
AU - Abu-Affash, A. Karim
AU - Carmi, Paz
AU - Maman, Meytal
PY - 2024/09/10
Y2 - 2024/10/07
TI - Piercing Diametral Disks Induced by Edges of Maximum Spanning Trees
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 28
IS - 3
SE -
DO - 10.7155/jgaa.v28i3.2968
UR - https://jgaa.info/index.php/jgaa/article/view/2968
SP - 3-10
AB - <p>Let $P$ be a set of points in the plane and let $T$ be a maximum-weight spanning tree of $P$.<br />For an edge $(p,q)$, let $D_{pq}$ be the diametral disk induced by $(p,q)$, i.e., the disk having the segment $\overline{pq}$ as its diameter. Let $\cal{D}_T$ be the set of the diametral disks induced by the edges of $T$. <br />In this paper, we show that one point is sufficient to pierce all the disks in $\cal{D}_T$. <br />Actually, we show that the center of the smallest enclosing circle of $P$ is contained in all the disks of $\cal{D}_T$, and thus the piercing point can be computed in linear time.</p>
ER -