关键词: 几何最小直径树, 最远点Voronoi图, 可分点集, 二中心问题

Abstract: For a planar point set P with n points, the geometric minimum-diameter spanning tree (MDST) problem has been studied extensively since 1991. The MDST problem of P is a tree that spans P and minimizes the Euclidean length of the longest path. HO et al.(1991) showed that there always exists an MDST which is either a monopolar(MDMST) or a dipolar(MDDST). The more difficult dipolar case can be computed in O(n³) time using O(n) space. The algorithms of finding the MDST of P in less than cubic time have recently been a subject of great interest. The cubic time algorithm has been improved to O(n^17/6) time by CHAN(2003). However, there is still no exact algorithm solving the MDST problem in less than O(n²) time. Note that, the MDST problem can be seen as the facility location problem and can be regarded as a variation of one-center and two-center problems. The more difficult dipolar case can also be considered as two disks covering the point set P. For two-center problem and minimum-sum dipolar spanning tree problem, the optimal structure contains the two disks covering the points which satisfy the perpendicular bisector of the two dipolar points separate P, respectively. However, the dipolar spanning tree may not satisfy the above optimal structure. Thus, finding the geometric property for dipolar spanning tree and the special point sets whose MDST can be solved in O(n²) time is the primary job in this paper.
If there is a line separating P into two parts P₁, P₂ and P₁, P₂ are on different sides of the line, the point set P is called separatable. The MDMST for a point set P can be computed in O(nlogn) time. The MDDST for a separable point set P can be seen as the smaller one between the minimum diameter dipolar spanning tree whose two dipoles are in two separated subsets, respectively(denoted as MsDDST) and the minimum diameter dipolar spanning tree whose two dipoles are both in one subset(denoted as McDDST). For a special case of the separable point set, finding the MDDST can be implemented in quadratic time. From the definition of MsDDST, it takes O(nlogn) time to compute the farthest Voronoi diagram of P₁ and P₂. For each point p, assign the distance w(p) between p and its farthest point in the subset which p belongs to. Finally find two points {p,q} in each subset to minimize w(p)+d(p,q)+w(q). This needs at most O(n²) time
This paper shows that if d≥max{d₁,d₂}, where d is the minimum distance between P₁ and P₂, d₁(resp. d₂) is the diameter of P₁ (resp. P₂), both the following two cases can be computed in no more than O(n²) time. Case1: if there is only one point in a subset, the MDST is an MDMST which can be computed in O(nlogn) time. Case2: if there are at least two points in each subset, the diameter of McDDST is larger than or equal to MsDDST's. In conclusion, if d≥max{d₁,d₂}, the MDST of P is either an MDMST or an MsDDST which can be computed in O(n²) time using O(n) space.

Key words: geometric minimum diameter spanning tree, farthest point Voronoi diagram, separable point set, 2-center problem