Rectilinear Steiner tree

The problem may be formally stated as follows: given n points in the plane, it is required to interconnect them all by a shortest network which consists only of vertical and horizontal line segments.

The idea is that STSTs for a given point set essentially have only one "degree of freedom", which is the position of the horizontal trunk.

Therefore an optimal position of the trunk are defined by a median of the set of Y-coordinates of the points, which may be found in linear time.

A better approximation, called the refined single trunk tree (RST-T), may be found in O(n log n) time.

[5] A number of algorithms exist which start from the rectilinear minimum spanning tree (RMST; the minimum spanning tree in the plane with rectilinear distance) and try to decrease its length by introducing Steiner points.