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 L_{1} 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).

Assume z_{i}, z_{j} Z is a pair of distinct
terminals and let P_{T}(z_{i}, z_{j}) denote the unique path between z_{i}
and z_{j} in a tree T. The path consists of one or more edges connecting the nodes.

Consider the paths P_{SMT(Z)}(z_{i}, z_{j}) and P_{MST(Z)}(z_{i}, z_{j}). Note that the
latter can easily be computed. Pick an edge e P_{SMT(Z)}(z_{i}, z_{j}) and remove
it from SMT(Z). This breaks the tree into two connected components that
contain each of the terminals z_{i} and z_{j} respectively. Now follow the path
P_{SMT(Z)}(z_{i}, z_{j}) which only consists of edges connecting terminals. One of
the edges on this path, say f = (z_{k}, z_{l}) will reconnect the two components
of the broken SMT. Clearly we must have that |e| |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, b_{zi}_{zj}, between a pair of terminals z_{i} and z_{j} is equal to the length
of the longest edge on P_{MST(Z)}(z_{i}, z_{j}). Note that there exists no terminal path between zi and zj
for which the longest edge is smaller than b_{zi}_{zj}.

**Lemma 3.1.** *For any edge e P _{SMT(Z)}(z_{i}, z_{j}) we have |e| b_{zi}_{zj}.*

Bottleneck Steiner distances between every pair of terminals can be determined in O(n^{2}) 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.

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:

also denoted the "lune" given by (u, v) (Figure 12a). The lune is the intersection between the interior of two L_{1} 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