The minimum area spanning tree problem.

Abstract. Motivated by optimization problems in sensor coverage, we formulate and study the Minimum-Area Spanning Tree (mast) problem: Given a set P of n points in the plane, find a spanning tree of P of minimum “area, ” where the area of a spanning tree T is the area of the union of the n − 1 disks whose diameters are the edges in T. We prove that the Euclidean minimum spanning tree of 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. 1