k度Steiner最小权网络的线性时间算法

已知平面上n个固定点集合N和m个可动点集合M，求互连点集N∪M的最短连通网络，要求这个连通网络满足：（1）固定点的度为1，可动点的度为k(k≥3）；（2）n=2 （k-2）m。网络中每条边的权与可动点的位置有关，问题是如何确定这m个可动点的位置，使这个连通网络的权最小，这个问题称为k度Steiner最小权网络问题。本给出了k为偶数，边权值为L1距离时计算最小权网络的O(n ln k)时间算法。