{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,10]],"date-time":"2026-10-10T00:57:57Z","timestamp":1791593877450,"version":"4.3.4"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1982,11]]},"abstract":"<jats:p>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 \\geqq 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 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.<\/jats:p>","DOI":"10.1137\/0211059","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:24:24Z","timestamp":1109226264000},"page":"721-736","source":"Crossref","is-referenced-by-count":404,"title":["On Constructing Minimum Spanning Trees in\n                    <i>k<\/i>\n                    -Dimensional Spaces and Related Problems"],"prefix":"10.1137","volume":"11","author":[{"given":"Andrew Chi-Chih","family":"Yao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R2","unstructured":"J. L. Bentley, J. H. Friedman,  Fast algorithms for constructing minimal spanning trees in coordinate spaces, Rep., STAN-CS-75-529, Stanford Computer Science Department, Stanford, CA,  1976, January"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Jon Louis Bentley, Michael Ian Shamos,  Divide-and-conquer in multidimensional space,  Eighth Annual ACM Symposium on Theory of Computing (Hershey, Pa., 1976), Assoc. Comput. Mach., New York,  1976,  220\u2013230 55:138690365.68050","DOI":"10.1145\/800113.803652"},{"key":"R4","volume-title":"Programming, Games, and Transportation Networks","author":"Bergs C.","year":"1965"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1943.11991447"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0205051"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0205015"},{"key":"R9","volume-title":"Pattern Classification and Science Analysis","author":"Dude R. O.","year":"1973"},{"key":"R10","volume":"1961","author":"Hocking John G.","year":"1961","journal-title":"Addison-Wesley Publishing Co., Inc., Reading, Mass.-London"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"A. Kerschenbaum, R. Van Slyke,  Computing minimum spanning trees efficiently,  Proc. 25th Annual Conference of the ACM,  1972,  518\u2013527","DOI":"10.1145\/800193.569966"},{"key":"R12","volume-title":"The art of computer programming. Volume 3","author":"Knuth Donald E.","year":"1973"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Michael Ian Shamos,  Geometric complexity,  Seventh Annual ACM Symposium on Theory of Computing (Albuquerque, N.M., 1975), Assoc. Comput. Mach., New York,  1975,  224\u2013233 57:46280357.68046","DOI":"10.1145\/800116.803772"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.8"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(75)90056-3"},{"key":"R18","unstructured":"A. C. Yao,  On computing the distance matrix of  n points in  k dimensions, IBM San Jose Research Center Technical Report, to appear"},{"key":"R19","unstructured":"A. C. Yao,  On the preprocessing cost in multidimensional search, IBM San Jose Research Center Technical Report, to appear"},{"key":"R20","unstructured":"A. C. Yao, F. F. Yao,  On computing the rank function for a set of vectors, Rep., UIUCDCS-R-75-699, Computer Science Department, University of Illinois, Illinois,  1975, Februrary"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223083"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0211059","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:59Z","timestamp":1787337659000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0211059"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,11]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1982,11]]}},"alternative-id":["10.1137\/0211059"],"URL":"https:\/\/doi.org\/10.1137\/0211059","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1982,11]]}}}