The minimal spanning tree and the upper box dimension

DOI10.1090/S0002-9939-05-08061-5MaRDI QIDQ3372096zbMATH OpenFDO

Authors Gady Kozma, Zvi Lotker, Gideon Stupp

Publication date 17 February 2006

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0311481

Mathematics Subject Classification ID

Trees (05C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We show that the alpha-weight of an MST over n points in a metric space with upper box dimension d has a bound independent of n if alpha is smaller than d and does not have one if alpha is larger than d.

Recommendations

• scientific article; zbMATH DE number 1436136
• The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach
• Minimum Spanning Trees in k-Dimensional Space
• Minimum spanning trees in d dimensions
• Growth rates of Euclidean minimal spanning trees with power weighted edges

Cites work

• scientific article; zbMATH DE number 44693 (Why is no real title available?)
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• scientific article; zbMATH DE number 1369841 (Why is no real title available?)
• On the Shortest Path Through a Number of Points
• On the length of optimal TSP circuits in sets of bounded diameter
• Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
• Steiner Minimal Trees
• The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees
• The shortest path and the shortest road through n points
• Worst case asymptotics for some classical optimization problems
• Worst case asymptotics of power-weighted Euclidean functionals

Cited in

(9)

• A fractal dimension for measures via persistent homology
• Persistent homology and the upper box dimension
• Rectilinear spanning trees versus bounding boxes
• On a traveling salesman problem for points in the unit cube
• Fractal dimension and the persistent homology of random geometric complexes
• Remez-type inequality for discrete sets
• On the connectivity threshold for general uniform metric spaces
• The MST of symmetric disk graphs (in arbitrary metric spaces) is light
• The MST of symmetric disk graphs (in arbitrary metric spaces) is light

This page was built for publication: The minimal spanning tree and the upper box dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3372096)