|
The minimal spanning tree and the upper box dimension
Author(s):
Gady
Kozma;
Zvi
Lotker;
Gideon
Stupp
Journal:
Proc. Amer. Math. Soc.
134
(2006),
1183-1187.
MSC (2000):
Primary 68U05, 05C05
Posted:
September 20, 2005
Retrieve article in:
PDF
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:
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
Copyright of article:
Copyright
2005,
American Mathematical Society
|
Comments: webmaster@ams.org