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. .
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.