Steiner Minimum Trees in Uniform Orientation Metrics

Let N be a set of points in the plane. Informally, the Steiner tree problem asks us to construct a network, known as a Steiner minimum network or Steiner minimum tree, interconnecting the points in N, such that the network has the shortest length possible with respect to a given distance function. Unlike minimum spanning trees, a Steiner minimum tree may contain vertices of degree 3 or more not in N. These points are usually referred to as Steiner points, and the inclusion of these points makes the Steiner problem an NP-hard problem.