Abstract: To the case k = 3 of the Berman`s approximation algorithm, the improved algorithm is proposed in this study. It constructs a Voronoi region to get the cost of triple subtree on the basis of using Fibonacci heap to count the shortest distance of each pair of points in the corresponding set. Then, to decrease useless triples by the topology analysis of Steinertree, it simplifies the topology and reduces the time complexity. In the experiment results, the filter factor β is above 0.9 for each example, some even up to 0.999. It shows that many useless triples have been filtered before the beginning of the evaluation phase and the construction phase.