On Improved Bounds for Bounded Degree Spanning Trees for Points in Arbitrary Dimension

Given points in Euclidean space of arbitrary dimension, we prove that there exists a spanning tree having no vertices of degree greater than 3 with weight at most 1.559 times the weight of the minimum spanning tree. We also prove that there is a set of points such that no spanning tree of maximal degree 3 exists that has this ratio be less than 1.447. Our central result is based on the proof of the following claim: Given n points in Euclidean space with one special point v, there exists a Hamiltonian path with an endpoint at v that is at most 1.559 times longer than the sum of the distances of the points to v. These proofs also lead to a way to find the tree in linear time given the minimal spanning tree.