The Minimum-Area Spanning Tree Problem

Motivated by optimization problems in sensor coverage, we formulate and study the Minimum-Area Spanning Tree (mast) problem: Given a set $\mathcal{P}$ of n points in the plane, find a spanning tree of $\mathcal{P}$ of minimum “area,” where the area of a spanning tree $\mathcal{T}$ is the area of the union of the n–1 disks whose diameters are the edges in $\mathcal{T}$. We prove that the Euclidean minimum spanning tree of $\mathcal{P}$ is a constant-factor approximation for mast. We then apply this result to obtain constant-factor approximations for the Minimum-Area Range Assignment (mara) problem, for the Minimum-Area Connected Disk Graph (macdg) problem, and for the Minimum-Area Tour (mat) problem. The first problem is a variant of the power assignment problem in radio networks, the second problem is a related natural problem, and the third problem is a variant of the traveling salesman problem.