BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-77-642
       ENTRY:: June 28, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On constructing minimum spanning trees in k-dimensional
               spaces and related problems
        TYPE:: Technical Report
      AUTHOR:: Yao, Andrew Chi-Chih
        DATE:: December 1977
       PAGES:: 40
    ABSTRACT:: The problem of finding a minimum spanning tree connecting n
               points in a k-dimensional space is discussed under three
               common distance metrics -- Euclidean, rectilinear, and
               $L_\infty$. By employing a subroutine that solves the post
               office problem, we show that, for fixed k $\geq$ 3, such a
               minimum spanning tree can be found in time O($n^{2-a(k)}
               {(log n)}^{1-a(k)}$), where a(k) = $2^{-(k+1)}$. The bound
               can be improved to O(${(n log n)}^{1.8}$) for points in the
               3-dimensional Euclidean space. We also obtain o($n^2$)
               algorithms for finding a farthest pair in a set of n points
               and for other related problems.
       NOTES:: [Adminitrivia V1/Prg/19950628]
         END:: STAN//CS-TR-77-642