Anchored dilation bounded minimum spanning tree

Abstract

A geometric network is a weighted undirected graph $\sl{G}$ whose vertices are points in $\mathbb{R}^d$, and weights are the Euclidean length of its edges. The graph distance between the two vertices in a geometric network is the length of shortest path connecting those points. The dilation of $\sl{G}$ is the maximum factor by which graph distance differs from the Euclidean distance between two points. The anchored dilation of $\sl{G}$ is the dilation from an anchor, a fixed given point, to other vertices. We consider the Anchored Dilation Bounded Minimum Spanning Tree(ADBMST) Problem. The problem is to build the spanning tree which has the minimum weight among all spanning trees with the anchored dilation at most $\delta$ for a given set of $\sl{n}$ points S and maximum dilation $\delta > 1$. I show that the problem is NP-hard by showing that there is a polynomial reduction from the Knapsack Problem to ADBMST Problem. I also suggest a simple algorithm to build an approximated tree.