Skip to main content
added a remark about exploiting the degree bound in MST calculations
Source Link
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

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.

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?

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.

explained the MST acronym
Source Link
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

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?

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

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?

Source Link
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

Maximal Vertex Degree of MSTs in Euclidean Spaces

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