{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:16Z","timestamp":1787337556406,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in $\\mathbb R^d$. We focus on the setting where the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within $1 + \\eps$ using only $\\widetilde{\\O}(\\sqrt{n} \\, \\text{poly} (1\/\\eps))$ queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbor queries.<\/jats:p>","DOI":"10.1137\/s0097539703435297","type":"journal-article","created":{"date-parts":[[2005,10,5]],"date-time":"2005-10-05T21:00:22Z","timestamp":1128546022000},"page":"91-109","source":"Crossref","is-referenced-by-count":41,"title":["Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time"],"prefix":"10.1137","volume":"35","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Funda","family":"Erg\u00fcn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avner","family":"Magen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"Pankaj Agarwal, Range searching, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, 575\u20135981730187"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574698"},{"key":"R3","unstructured":"Pankaj Agarwal, Jeff Erickson, Geometric range searching and its relatives, Contemp. Math., Vol. 223, Amer. Math. Soc., Providence, RI, 1999, 1\u20135699m:68203"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00014-0"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523237"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03427-9"},{"key":"R7","unstructured":"Paul Callahan, S. Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, ACM, New York, 1993, 291\u201330094a:05184"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0215051"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"R10","unstructured":"Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan, Approximating the minimum spanning tree weight in sublinear time, Lecture Notes in Comput. Sci., Vol. 2076, Springer, Berlin, 2001, 190\u20132002065862"},{"key":"R11","unstructured":"Artur Czumaj, Christian Sohler, Property testing with geometric queries (extended abstract), Lecture Notes in Comput. Sci., Vol. 2161, Springer, Berlin, 2001, 266\u20132771914041"},{"key":"R12","unstructured":"Artur Czumaj, Christian Sohler, Estimating the weight of metric minimum spanning trees in sublinear\u2010time, ACM, New York, 2004, 175\u20131832005j:68126"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758755"},{"key":"R14","unstructured":"David Eppstein, Spanning trees and spanners, North\u2010Holland, Amsterdam, 2000, 425\u20134611746681"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574030"},{"key":"R16","unstructured":"J. Erickson,\n                      On the relative complexity of some geometric problems\n                      , in Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG), Quebec City, 1995, pp. 85\u201390."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382947"},{"key":"R18","unstructured":"Piotr Indyk, Algorithms for dynamic geometric problems over data streams, ACM, New York, 2004, 373\u20133802121621"},{"key":"R19","unstructured":"R. Karp, J. Steele, Probabilistic analysis of heuristics, Wiley\u2010Intersci. Ser. Discrete Math., Wiley, Chichester, 1985, 181\u2013205811473"},{"key":"R20","unstructured":"George Lueker, A data structure for orthogonal range queries, IEEE, Long Beach, Calif., 1978, 28\u20133480e:68047"},{"key":"R21","unstructured":"J. Ruppert and R. Seidel,\n                      Approximating the d\u2010dimensional complete Euclidean graph\n                      , in Proceedings of the 3rd Canadian Conference on Computational Geometry (CCCG), Vancouver, 1991, pp. 207\u2013210."},{"key":"R22","unstructured":"Michael Shamos, Dan Hoey, Closest\u2010point problems, IEEE Computer Society, Long Beach, Calif., 1975, 151\u201316254:14441"},{"key":"R23","unstructured":"C. Sohler,\n                      Property Testing and Geometry\n                      , Ph.D. dissertation, HNI\u2010Verlags schriften\u2010 reihe, Vol. 119, Heinz\u2010Nixdorf Institut and University of Paderborn, 2003;"},{"key":"R23","unstructured":"available from http:\/\/www.upb.de\/fachbereich\/AG\/agmadh\/WWW\/english\/csohler\/Diss.ps.gz."},{"key":"R24","volume-title":"Approximation algorithms","author":"Vazirani Vijay","year":"2001"},{"key":"R25","unstructured":"D. E. Willard,\n                      Predicate\u2010Oriented Database Search Algorithms\n                      , Ph.D. thesis (report TR\u201020\u201078), Harvard University, Aiken Computation Lab, Cambridge, MA, 1978."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0211059"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539703435297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:17:21Z","timestamp":1787336241000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539703435297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0097539703435297"],"URL":"https:\/\/doi.org\/10.1137\/s0097539703435297","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}