论文标题
最大跨越树的边缘引起的刺穿直径盘
Piercing Diametral Disks Induced by Edges of Maximum Spanning Tree
论文作者
论文摘要
让$ p $是飞机上的一组点，让$ t $成为$ p $的最大重量跨越树。对于边缘$（p，q）$，令$ d_ {pq} $为$（p，q）$诱导的直径盘，即具有段$ \ overline {pq} $的磁盘作为直径。令$ \ cal {d_t} $为$ t $的边缘引起的直径盘的集合。在本文中，我们表明一个点足以将所有磁盘刺穿$ \ cal {d_t} $，因此，集合$ \ cal {d_t} $是helly。实际上，我们表明，$ p $的最小封闭圆的中心包含在$ \ cal {d_t} $的所有磁盘中，因此可以在线性时间内计算穿孔点。
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}$, thus, the set $\cal{D_T}$ is Helly. 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.
