本文首先介绍了超大规模集成电路的物理设计流程,在此基础上引出直角斯坦纳树问题。许多已知算法考虑了有障碍的直角斯坦纳树问题,但是对于布线区域存在边界的情况并没有涉及。布线区域的边界不能简单地看作一维障碍的拼接,因为这样会把凹的边界切割下去,从而使导线跑到布线区域外边。同时,在布线区域边界不规则时会带来不必要的运算。本文介绍的赋权李算法就很好地克服了这个问题。该算法的时间复杂度为O(n~2(n+m)~2log(n+m)),其中n是终端的个数,m是障碍和边界的顶点个数之和。同时本文提出了最小凸多边形的技术,大大缩减了布线区域的面积,并且证明了在这个最小凸多边形中存在最优解,然后利用改进的赋权李算法,给出次优解。本文提到的算法,可以在运算中剔除不需要考虑的障碍,从而进一步减小运算规模。实践证明,该算法在布线区域边界不规则,且终端成对角线状排列时,能获得最高的效率。对于多层布线的模型,本文将赋权李算法扩展到三维,同时将最小凸多边形的技术扩展到最小凸多面体,通过调整扩展的Hanan格对应边的权重,从而达到了减少通孔的目的。最后本文给出了在更高维空间的直角斯坦纳树问题的定义,和相应的最小凸多面体的构造。