Piercing Diametral Disks Induced by Edges of Maximum Spanning Trees

A. Karim Abu-Affash¹ ; Paz Carmi² ; Meytal Maman²

¹ Shamoon College of Engineering
² Ben-Gurion University

Journal of Graph Algorithms and Applications, Special issue on Selected Papers from the 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023 , Tome 28 (2024) no. 3, pp. 3-10.

Résumé

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 $\overline{pq}$ as its diameter. Let $\cal{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 $\cal{D}_T$. 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.

Détail

DOI : 10.7155/jgaa.v28i3.2968

Keywords: Maximum spanning tree, Piercing set, Helly’s Theorem, Fingerhut's Conjecture