Notation

The notation used on these pages is primary taken from Rectilinear Full Steiner Tree Generation and The Rectilinear Steiner Tree Problem: A Tutorial both by Martin Zachariasen. In figure 8 you can se some of the terms used graphically. The use of distinct circles for non-terminals is our own. .


Steiner tree with notation

Figure 8: Notation


Line segments:
Horizontal and vertical lines that is only crossing in their endpoints. Shown as a black line.
Point
Endpoint for line segment. It can be, a terminal or a non-terminal.
Terminal
Point belonging to the given set Z of points that the Steiner tree shall span. Shown as a filed black circle.
Non-terminal
Either:
Corner point
Is shown as a black circle with gray fill.
T-point.
Is shown as a black circle ring without fill.
Cross-point.
Is shown as a black circle ring without fill.
Corner point
A point that is the end for two complete lines perpendicular to each other. Has degree 2.
T-point
A point where two perpendicular line segments meets, and the point is the end for one of the lines but not the other. Has degree 3.
Cross-point
A point where to perpendicular line segments meet and the point is not the end for either line segment. Has degree 4.
Backbone.
A sequence of one or more adjacent, collinear segments with no terminal sharing two adjacent segments. Endpoints may be terminals.
Complete line
A line of segments of maximal length. It is not properly contained in any other line of segments. The line from A to C in fig.1 is a complete line.
Complete corner
The two perpendicular complete lines meeting at a corner point. In fig.1 the lines AC and CB makes a complete corner.
Leg
The lines that makes up a complete corner. In fig.1 is A2C the long leg and CB the short leg.
Steiner-point
A point that does not belong to the given set Z of points, which added to Z makes it possibly to make a tree of minimum length.
Empty region
A region where there can be no points in a Steiner Minimum Tree (SMT). Shown as a transparent gray area.