Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
3 of 3
added a remark about exploiting the degree bound in MST calculations
Manfred Weis
  • 14k
  • 4
  • 39
  • 82

Maximal Vertex Degree of MSTs in Euclidean Spaces

Are there any Euclidean spaces, in which the maximal vertex degree of MSTs (Minimum Spanning Trees) of a finite set of points and edge weights equal to Euclidean distance, isn't equal to the kissing number?

Remark:
The fact, that the kissing number is an upper bound on the vertex degree of MSTs of Euclidean spaces can be exploited for reducing the memory footprint for calculating those MSTs; instead of feeding $\frac{n(n-1)}{2}$ distances into the MST algorithm, it suffices to provide only the $k$ smallest distances for each vertex, where $k$ is the kissing number of the respective Euclidean space.

Manfred Weis
  • 14k
  • 4
  • 39
  • 82