2. Fixed Orientation Steiner Trees

The results of Widmayer et al. [400, 401] were also anticipated, in part, by earlier and contemporary papers such as [408] and [385].

The norms associated with the class of fixed orientation metrics have been referred to in the literature as ‘polyhedral norms’, in [408], or ‘block norms’, in [385]. Moreover, if we relax the condition that the polygon \(\mathcal{C}\) is centrally symmetric, then rather than having an associated norm, we have an associated gauge; see [145] for more details.

The first proof of Theorem 2.5 was given by Sarrafzadeh and Wong [338], albeit not covering the case where λ is a multiple of 3 correctly. Alternative (and correct) proofs using various proof techniques were given by Koh [235] (only for λ = 4), Li et al. [256] (only lower bounds), Brazil et al. [65], Swanepoel [358], Hayase [189] and Il’yutko [217].

Note that in λ-geometry these direction sets are the same as the ‘feasible direction sets’ defined in [70].

This theorem can be strengthened to include a lower bound of σ on the number of complementary coloured direction sets. This follows by proving a converse to Theorem 1.​28 showing that every set of supporting lines satisfying the centroid property corresponds to a Steiner configuration. The details can be found in [74], where some of the arguments rely on results from [274]. The main consequence of this lower bound is to show that the time complexity of the linear-time enumeration algorithm developed at the end of this section cannot be improved.

Zero-shifts were introduced by Du and Hwang [136] for λ = 3, and originally used as a technical tool in the quest for better bounds on the size of the generalised Hanan grid [235, 244, 245].

In 1999, Thurber and Xue [368] gave a linear programming formulation for the λ = 3 case, and in 2002, Xue and Thulasiraman [417] generalised the formulation to the general uniform orientation metric. Zachariasen [430] pointed out a non-trivial error in this formulation and presented a new and correct formulation, now generalised to all fixed orientation metrics. This latter formulation is the one briefly presented here.

Subsequently Li et al. [255] gave a simple algorithm to construct this triangular region based on finding median points and so-called mid-orientation lines. More generally, Shen [346] and Hayase [189] independently showed that when λ is a multiple of 3, the feasible region (called a ‘public domain’ in [346] and a ‘diamond area’ in [189]) is a convex polygon with up to six vertices; when λ is not a multiple of 3, then the minimum Steiner tree for three terminals is unique and the feasible region contains a single point.

This theorem has been shown over time to hold for increasingly larger classes of fixed orientation problems. In 1992 Du and Hwang [136] proved that Theorem 2.29 holds for λ = 3 (uniform metric with three orientations). They also conjectured that for any i > 0 there exists a fixed orientation metric and a terminal set N such that all minimum Steiner trees for N have some Steiner point not in GG _i (N). In other words, they conjectured that the bound n − 2 in Theorem 2.29 cannot be reduced to a constant. In 1995 Koh [235] and Lee et al. [245] independently proved that the theorem holds for λ = 4 by showing that it is always possible to perform zero-shifts such that some Steiner point is connected to two terminals using straight edges only. In 1996 Lee and Shen [244] generalised the result to any λ (or uniform orientation metric) using the same proof technique. In 2001 Li et al. [257] showed that Theorem 2.29 holds for all unweighted fixed orientation metrics. Finally, in 2009 Brazil and Zachariasen [74] implicitly proved that the theorem also holds for the weighted case; this was first stated explicitly later that year by Zachariasen [431].