An Approximation Scheme for the Generalized Geometric Minimum Spanning Tree Problem with Grid Clustering

This paper is concerned with a special case of the Generalized Minimum Spanning Tree Problem. The Generalized Minimum Spanning Tree Problem is de¯ned on an undirected graph, where the vertex set is partitioned into clusters, and non-negative costs are associated with the edges. The problem is to ¯nd a tree of minimum cost containing exactly one vertex in each cluster. We consider a geometric case of the problem where the graph is complete, all vertices are situated in the plane, and Euclidean distance de¯nes the edge cost. We prove that the problem admits PTAS if restricted to grid clustering.