Advertisement
Published in:
2007 | OriginalPaper | Chapter
Rotational Steiner Ratio Problem Under Uniform Orientation Metrics
Authors : Songpu Shang, Xiaodong Hu, Tong Jing
Published in: Discrete Geometry, Combinatorics and Graph Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Let
P
be a set of
n
points in a metric space. A Steiner Minimal Tree (SMT) on
P
is a shortest network interconnecting
P
while a Minimum Spanning Tree (MST) is a shortest network interconnecting
P
with all edges between points of
P
. The Steiner ratio is the infimum over
P
of ratio of the length of SMT over that of MST. Steiner ratio problem is to determine the value of the ratio. In this paper we consider the Steiner ratio problem in uniform orientation metrics, which find important applications in VLSI design. Our study is based on the fact that lengths of MSTs and SMTs could be reduced through properly rotating coordinate systems without increasing the number of orientation directions. We obtain the Steiner ratios with |
P
| = 3 when rotation is allowed and some bounds of Steiner ratios for general case.