On the Longest Spanning Tree with Neighborhoods

We study a maximization problem for geometric network design. Given a set of $n$ compact neighborhoods in ${\mathbb{R}}^d$, select a point in each neighborhood, so that the longest spanning tree on these points (as vertices) has maximum length. Here we give an approximation algorithm with ratio $0.511$, which represents the first, albeit small, improvement beyond $1\mathrm{/}2$. While we suspect that the problem is NP-hard already in the plane, this issue remains open.