|
The minimal spanning tree and the upper box dimension
Authors:
Gady Kozma, Zvi Lotker and Gideon Stupp
Journal:
Proc. Amer. Math. Soc. 134 (2006), 1183-1187
MSC (2000):
Primary 68U05, 05C05
Posted:
September 20, 2005
MathSciNet review:
2196055
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We show that the  -weight of an MST over  points in a metric space with upper box dimension  has a bound independent of  if  and does not have one if  .
References
- [ABNW99]
Michael Aizenman, Almut Burchard, Charles M. Newman and David B. Wilson, Scaling limit for minimal and random spanning trees in two dimensions, Random Structures and Algorithms 15:3-4 (1999), 319-367. http://arxiv.org/abs/math.PR/9809145 MR 1716768 (2001c:60151)
- [AS04]
David Aldous and J. Michael Steele, The objective method: probabilistic combinatorical optimization and local weak convergence, Probability on discrete structures, 1-72, Encyclopaedia Math. Sci., 110, Springer, Berlin, 2004. http://stat-www.berkeley.edu/users/aldous/me101.ps.Z
- [A96]
Kenneth S. Alexander, The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees, Ann. Appl. Probability 6 (1996), 466-494. MR 1398054 (97f:60204)
- [CLR91]
Thomas H. Corman, Charles E. Leiserson and Ronald L. Rivest, Introduction to algorithms, MIT Press, 1991.
- [FT40]
L. T. Fejes-Tóth, Uber einen geometrische Satz, Mathematische Zeitschrift 46 (1940), 83-85. MR 0001587 (1:263g)
- [F55]
L. Few, The shortest path and the shortest road through
 points in a region, Mathematika 2 (1955), 141-144. MR 0078715 (17:1235f)
- [F90]
K. Falconer, Fractal geometry, mathematical foundations and applications, John Wiley & Sons, New York, 1990. MR 1102677 (92j:28008)
- [GP68]
E. N. Gilbert and H. O. Pollak, Steiner random minimal trees, SIAM J. Appl. Math. 16 (1968), 1-29. MR 0223269 (36:6317)
- [L02]
Sungchul Lee, Worst case asymptotics of power-weighted Euclidean functionals, Discrete Math. 256:1-2 (2002), 291-300. http://suny.yonsei.ac.kr/ filab/paper/9.ps MR 1927073 (2003g:05076)
- [M84]
S. Moran, On the length of optimal TSP circuits in sets of bounded diameter, J. Combinatorial Theory Ser. B 37 (1984), 113-141. MR 0766629 (86i:05087)
- [SS87]
T. L. Snyder and J. Michael Steele, Worst case growth rates for minimal and greedy matchings with power weighted edges, Technical report, Princeton University, Program in Operations Research and Statistics (1987).
- [S90]
J. Michael Steele, Probabilistic and worst case analyses of classical problems of combinatorial optimization in Euclidean space, Mathematics of Operations Research 15:4 (1990), 749-770. MR 1080476 (92e:68080)
- [V51]
S. Verblunsky, On the shortest path through a number of points, Proc. Amer. Math. Soc. 2 (1951), 904-913. MR 0045403 (13:577c)
- [Y96]
Joseph E. Yukich, Worst case growth rates for some classical optimization problems, Combinatorica 16 (1996), 575-586. MR 1433644 (97i:90061)
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC (2000):
68U05,
05C05
Retrieve articles in all journals
with MSC (2000):
68U05,
05C05
Additional Information
Gady Kozma
Affiliation:
Institute for Advanced Study, 1 Einstein Drive, Princeton, New Jersey 08540
Email:
gady@ias.edu
Zvi Lotker
Affiliation:
Office Centrum voor Wiskunde en Informatica, Kruislaan, 413, NL-1098 SJ Amsterdam, The Netherlands
Email:
zvilo@eng.tau.ac.il
Gideon Stupp
Affiliation:
MIT Computer Science and Artificial Intelligence Laboratory, The Stata Center, 32 Vassar Street, Cambridge, Massachusetts 02139
Email:
gstupp@theory.csail.mit.edu
DOI:
http://dx.doi.org/10.1090/S0002-9939-05-08061-5
PII:
S 0002-9939(05)08061-5
Received by editor(s):
January 7, 2004
Received by editor(s) in revised form:
October 25, 2004
Posted:
September 20, 2005
Communicated by:
John R. Stembridge
Article copyright:
© Copyright 2005 American Mathematical Society
|
