Flexibility of steiner trees in uniform orientation metrics
We present some fundamental flexibility properties for minimum length networks (known as Steiner minimum trees) interconnecting a given set of points in an environment in which edge segments are restricted to lambda uniformly oriented directions. These networks are referred to as lambda-SMTs. They promise to play an increasingly important role in the future of optimal wire routing in VLSI physical design, particularly for the next generation of VLSI circuits. In this article we develop the concept of a flexibility polygon for a lambda-SMT, which is a region representing the union of all lambda-SMTs with the same topology on a given set of points. We show that this polygon can be constructed, for a given point set and given topology, in linear time. We discuss some of the future applications of this polygon, which can be thought of as a geometric representation of the amount of flexibility inherent in a given lambda-SMT. (c) 2005 Wiley Periodicals, Inc.
flexibility interconnection networks uniform orientation steiner trees vlsi design