@article{07e3f0d43c824d1f8c8c1e3d64b56faa, title = "An approximation scheme for some Steiner tree problems in the plane", abstract = "We design a polynomial-time approximation scheme for the Steiner tree problem in the plane when the given set of regular points is c-local, i.e., in the minimum-cost spanning tree for the given set of regular points, the length of the longest edge is at most c times the length of the shortest edge. The algorithm works for both Euclidean and rectilinear metrics. For a fixed number k, the performance ratio of our algorithm is 1 + (35c/√3k) for the Euclidean metric and 1 + (9c/k) for the rectilinear metric. Thus, when k increases, the performance ratio approaches 1.", author = "Lusheng Wang and Tao Jiang", year = "1996", month = dec, doi = "10.1002/(SICI)1097-0037(199612)28:4<187::AID-NET3>3.0.CO;2-H", language = "English", volume = "28", pages = "187--193", journal = "Networks", issn = "0028-3045", publisher = "John Wiley & Sons, Inc.", number = "4", }