Given a set S of n points in the plane, a minimum-dilation spanning tree of S is a tree with vertex set S of smallest possible dilation. We show that given a set S of n points and a dilation δ > 1, it is NP-hard to determine whether a spanning tree...
Given a set S of n points in the plane, a minimum-dilation spanning tree of S is a tree with vertex set S of smallest possible dilation. We show that given a set S of n points and a dilation δ > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most δ exists.