2019/11/19 by Biniaz, Ahmad · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1911.08529
Inspired by the seminal works of Khuller et al. (STOC 1994) and Chan (SoCG 2003) we study the bottleneck version of the Euclidean bounded-degree spanning tree problem. A bottleneck spanning tree is a spanning tree whose largest edge-length is minimum, and a bottleneck degree-K spanning tree is a degree-K spanning tree whose largest edge-length is minimum. Let βK be the supremum ratio of the largest edge-length of the bottleneck degree-K spanning tree to the largest edge-length of the bottleneck spanning tree, over all finite point sets in the Euclidean plane. It is known that β5=1, and it is easy to verify that β2≥ 2, β3≥ √(2), and β4>1.175. It is implied by the Hamiltonicity of the cube of the bottleneck spanning tree that β2≤ 3. The degree-3 spanning tree algorithm of Ravi et al. (STOC 1993) implies that β3≤ 2. Andersen and Ras (Networks, 68(4):302-314, 2016) showed that β4≤ √(3). We present the following improved bounds: β2≥√(7), β3≤ √(3), and β4≤ √(2). As a result, we obtain better approximation algorithms for Euclidean bottleneck degree-3 and degree-4 spanning trees. As parts of our proofs of these bounds we present some structural properties of the Euclidean minimum spanning tree which are of independent interest.