Optimality Conditions

An edge e = (u,v) in an SMT is a direct connection between a pair of nodes u and v (which are either terminals or Steiner points). In a fulsome and canonical SMT an edge is either a single segment or a pair of perpendicular segments adjacent at a corner point. The length of an edge e = (u,v) denoted by |e|, is the L1 distance between u and v.

In this section we give some bounds on the length of edges in SMTs; also we present some properties that particular configurations of edges must fulfill. Furthermore note that any subtree of an SMT clearly must be an SMT for the nodes spanned; in particular this holds for FSTs. Tests based on this condition are usually denoted upper bound tests, and can be applied by computing heuristic trees that span the set of nodes in question.

In order to simplify the exposition, we consider SMT(Z) and MST(Z) as being unique. It is easy to see that all optimality conditions given will be valid for any SMT(Z) and MST(Z).

Bottleneck Steiner Distance

Assume zi, zj is in Z is a pair of distinct terminals and let PT(zi, zj) denote the unique path between zi and zj in a tree T. The path consists of one or more edges connecting the nodes.

Consider the paths PSMT(Z)(zi, zj) and PMST(Z)(zi, zj). Note that the latter can easily be computed. Pick an edge e is in PSMT(Z)(zi, zj) and remove it from SMT(Z). This breaks the tree into two connected components that contain each of the terminals zi and zj respectively. Now follow the path PSMT(Z)(zi, zj) which only consists of edges connecting terminals. One of the edges on this path, say f = (zk, zl) will reconnect the two components of the broken SMT. Clearly we must have that |e| less than or equal |f| since otherwise we would have shown that SMT(Z) was not a shortest tree. This observation leads to the following definition. The Bottleneck Steiner distance, bzizj, between a pair of terminals zi and zj is equal to the length of the longest edge on PMST(Z)(zi, zj). Note that there exists no terminal path between zi and zj for which the longest edge is smaller than bzizj.

Lemma 3.1. For any edge e is in PSMT(Z)(zi, zj) we have |e| less than or equal bzizj.

Bottleneck Steiner distances between every pair of terminals can be determined in O(n2) time by computing MST(Z) and doing a depth first traversal in this tree from every terminal. The optimality condition provided by Lemma 3.1 turns out to be very powerful in practice.

Empty Regions

In the previous section we gave an upper bound on the length of edges connecting a pair of terminals. In this section we give some conditions that depend on how close other terminals are to an edge or a pair of edges. Let (u, v) be an edge in SMT(Z). Consider the region:

L(u,v) = {p is in R2 : |pu| < |uv| and |pv| > |uv|}

also denoted the "lune" given by (u, v) (Figure 12a). The lune is the intersection between the interior of two L1 circles with radius |uv| centered at u and v, respectively.

Lemma 3.2. If (u,v) is an edge in SMT(Z), then L(u,v) contains no other point (terminal, Steiner point, or interior segment point) from SMT(Z).

Text taken from: 'The Rectilinear Steiner Tree Problem: A Tutorial', Martin Zachariasen, 2001, pp. 15-17