In this paper we consider a basic clustering problem that has uses in bioinformatics. A structural fragment is a sequence of e points in a 3D space, where e is a fixed' natural number. Two structural fragments f_1 and f_2 are equivalent iff f_1 = f_2·R + τ under some rotation R and translation τ. We consider the distance between two structural fragments to be the sum of the Euclidean squared distance between all corresponding points of the structural fragments. Given a set of n structural fragments, we consider the problem of finding k (or fewer) structural fragments g_1, g_2 , ..., g_k, so as to minimize the sum of the distances between each of f_1, f_2,..., f_n to its nearest structural fragment in g_1,..., g_k. In this paper we show a PTAS for the problem through a simple sampling strategy.
展开▼
