Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

New Method for Rectilinear Steiner Trees

IP.com Disclosure Number: IPCOM000036191D
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 6 page(s) / 57K

Publishing Venue

IBM

Related People

Ho, JM: AUTHOR [+3]

Abstract

Disclosed is a new method for obtaining rectilinear Steiner trees. In this method, a rectilinear Minimum Spanning Tree (MST) is globally transformed into a Steiner tree, which is optimum under the operation of flipping the L-shaped edges of the MST. This new approach exploits some ideas that are specific to the rectilinear case and results in a Steiner tree algorithm that is fast, and produces lower cost Steiner trees than those given by previous techniques 3,6,7.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 22% of the total text.

Page 1 of 6

New Method for Rectilinear Steiner Trees

Disclosed is a new method for obtaining rectilinear Steiner trees. In this method, a rectilinear Minimum Spanning Tree (MST) is globally transformed into a Steiner tree, which is optimum under the operation of flipping the L-shaped edges of the MST. This new approach exploits some ideas that are specific to the rectilinear case and results in a Steiner tree algorithm that is fast, and produces lower cost Steiner trees than those given by previous techniques 3,6,7.

The two main notions in this approach are: Steiner Tree Draft derived from a Minimum Spanning Tree: A draft is a Steiner tree that is obtained by selecting one of the two flips for each L-shaped edge in the rectilinear MST, and merging any resulting overlaps. The optimum draft is the draft of the smallest total cost. Stability of a Rectilinear Steiner Tree: A Steiner tree is stable if no two L-shaped segments in the tree can be made to overlap or cross by flipping either or both of them.

Given a rectilinear MST of a set of points on the grid, each edge of the rectilinear MST can be regarded as an L-shaped segment between the two end points of the edge. If the two end points are on the same vertical or horizontal grid line, then the L-shaped segment connecting them is said to be degenerate; otherwise, it is said to be non-degenerate. The total cost of the rectilinear MST is simply the sum of the lengths of these L-shaped segments corresponding to the edges of the rectilinear MST. There are two ways of embedding a non- degenerate L-shaped segment, each of which is a flip of the other. Depending on which of these two flips we choose for each of the non-degenerate L- shapes, the total amount of overlaps among these L-shapes will be different. Merging of the overlapping portions will cause the introduction of Steiner points, and the result will be a Steiner tree. Depending on which set of flips we choose for the L- shaped segments, the resulting Steiner tree will have different costs. The cost of this Steiner tree will be smaller than the cost of the MST by the total amount of overlap among the embeddings of the L-shaped segments. The resulting Steiner tree is referred to as a draft derived from the rectilinear MST.

Definition 1: A draft derived from a rectilinear MST is a Steiner tree obtained by selecting one of the two possible flips for each non- degenerate L-shaped segment representing each edge of the MST, and by merging the resulting overlaps. The optimum draft is the draft of the smallest cost.

Consider a rectilinear Steiner tree of a set of points on a grid. A vertex in the Steiner tree is either an original point or a Steiner point. An edge in the tree, as before, is given by a degenerate or a non-degenerate L-shaped segment between two vertices of the tree. Suppose there exists two degenerate or non- degenerate L-shaped segments that can be made to cross or overlap by flipping either or both of them. If the two L-shaped segm...