繞線問題是超大型積體電路實體設計中非常重要的一部分，隨著半導體製程
不斷的進步，晶片電路複雜度也與日俱增，單位面積的繞線密度也隨之大幅提
升，繞線問題佔整體晶片設計效能的比例也提高了許多。然而，在現今積體電路
設計中，有越來越多的障礙物，這些障礙物主要是智財區塊(IP block)、動力網路
系統(power network)、已繞的繞線等，所以如何有效的決定繞線路徑來解決繞線
問題，是一個相當重要的研究議題。

我們考量一個給定的平面上存在著節點以及可重疊的直角障礙物，透過直線
以及橫線且可能經過額外的史坦納點的集合，連結所有的節點並避免穿越任何障
礙物，在可重疊的直角障礙物下，會產生個多個閉區間，使得最小線長的直角史
坦納樹會有多棵，最後建構出具有最小線長的直角史坦納森林。

在本篇論文中，我們提出一個新的避開重疊障礙物直角擴張森林建構的演算
法，此方法較以往相關的文獻，能進行更有效率的平面掃描，快速的建立避開障
礙物生成圖的時間。經由實際的模擬，我們的演算法能夠很可觀的減少障礙物生
成時間，且能夠處理重疊障礙物的情況。

In VLSI physical design, routing problem is an extremely important subject.
As the semiconductor technologies progress, the complexity of chip circuit increases
substantially. Thus, how to increase the efficiency in a physical circuit devise becomes
an important research subject.

Given a set of pins and a set of obstacles which can overlap each other on a
plane, an obstacle-avoiding rectilinear Steiner minimal forest (OARSMF) connects
these pins on each connected component, possibly through some additional points
(called Steiner points), and avoids running through any obstacle to construct a forest
with a minimal total wire-length.

In this paper, we propose an obstacle-avoiding rectilinear Steiner forest (OARSF)
construction algorithm. This method sweeps the plane more efficiently and constructs
obstacle-avoiding rectilinear graph (OASG)fast. In our work, the experimental
result shows our algorithm can reduce significant time to construct OASG
and deal with overlapping obstacles.

Bibliography
[1] C. Lin, S. Chen, C. Li, Y. Chang, and C. Yang, “Efficient obstacle-avoiding
rectilinear steiner tree construction,” in Proceedings of the 2007 international
symposium on Physical design. ACM, 2007, pp. 127–134.

[2] M. Garey and D. Johnson, “The rectilinear steiner tree problem is np-complete,”
SIAM Journal on Applied Mathematics, pp. 826–834, 1977.

[3] Z. Feng, Y. Hu, T. Jing, X. Hong, X. Hu, and G. Yan, “An o (n log n) algorithm
for obstacle-avoiding routing tree construction in the -geometry plane,” in
Proceedings of the 2006 international symposium on Physical design. ACM,
2006, pp. 48–55.

[4] R. Karp, Reducibility among combinatorial problems. Springer, 1972, vol. 40,
no. 4.

[5] M. Garey, R. Graham, and D. Johnson, “The complexity of computing steiner
minimal trees,” SIAM journal on applied mathematics, pp. 835–859, 1977.

[6] D. Du, Y. Zhang, and Q. Feng, “On better heuristic for euclidean steiner minimum
trees,” in 32nd Annual Symposium on Foundations of Computer Science,
1991. Proceedings. IEEE, 1991, pp. 431–439.

[7] J. Ho, G. Vijayan, and C. Wong, “New algorithms for the rectilinear steiner tree
problem,” IEEE Transactions on Computer-Aided Design of Integrated Circuits
and Systems, vol. 9, no. 2, pp. 185–193, 1990.

[8] Y. Yang, Q. Zhu, T. Jing, X. Hong, and Y. Wang, “Rectilinear steiner minimal
tree among obstacles,” in 5th International Conference on ASIC, 2003.
Proceedings., vol. 1. IEEE, 2003, pp. 348–351.

[9] Y. Hu, Z. Feng, T. Jing, X. Hong, Y. Yang, G. Yu, X. Hu, and G. Yan, “Forst:
A 3-step heuristic for obstacle-avoiding rectilinear steiner minimal tree construction,”
Journal of Information and Computational Science, vol. 1, no. 3,
pp. 107–116, 2004.

[10] K. Clarkson, S. Kapoor, and P. Vaidya, “Rectilinear shortest paths through
polygonal obstacles in o (n (log n) 2) time,” in Proceedings of the third annual
symposium on Computational geometry. ACM, 1987, pp. 251–257.

[11] Y. Wu, P. Widmayer, M. Schlag, and C. Wong, “Rectilinear shortest paths and
minimum spanning trees in the presence of rectilinear obstacles,” Computers,
IEEE Transactions on, vol. 100, no. 3, pp. 321–331, 1987.

[12] J. Ganley and J. Cohoon, “Routing a multi-terminal critical net: Steiner tree
construction in the presence of obstacles,” in 1994 IEEE International Symposium
on Circuits and Systems, 1994. ISCAS’94., vol. 1. IEEE, 1994, pp. 113–
116.

[13] S. Zheng, J. Lim, and S. Iyengar, “Finding obstacle-avoiding shortest paths using
implicit connection graphs,” IEEE Transactions on Computer-Aided Design
of Integrated Circuits and Systems, vol. 15, no. 1, pp. 103–110, 1996.
[14] P. Wu, J. Gao, and T. Wang, “A fast and stable algorithm for obstacle-avoiding
rectilinear steiner minimal tree construction,” in Proceedings of the 2007 Asia
and South Pacific Design Automation Conference. IEEE Computer Society,
2007, pp. 262–267.

[15] R. Hentschke, J. Narasimham, M. Johann, and R. Reis, “Maze routing steiner
trees with effective critical sink optimization,” in Proceedings of the 2007 international
symposium on Physical design. ACM, 2007, pp. 135–142.

[16] L. Li and E. Young, “Obstacle-avoiding rectilinear steiner tree construction,”
in Proceedings of the 2008 IEEE/ACM International Conference on Computer-
Aided Design. IEEE Press, 2008, pp. 523–528.

[17] Y. Lin, S. Chang, and Y. Li, “Critical-trunk based obstacle-avoiding rectilinear
steiner tree routings for delay and slack optimization,” in Proceedings of the
2009 international symposium on Physical design. ACM, 2009, pp. 151–158.

[18] Z. Shen, C. Chu, and Y. Li, “Efficient rectilinear steiner tree construction with
rectilinear blockages,” in ICCD 2005. Proceedings. 2005 IEEE International Conference on Computer Design: VLSI in Computers and Processors, 2005.
IEEE, 2005, pp. 38–44.

[19] L. Li, Z. Qian, and E. Young, “Generation of optimal obstacle-avoiding rectilinear
steiner minimum tree,” in Computer-Aided Design-Digest of Technical
Papers, 2009. ICCAD 2009. IEEE/ACM International Conference on. IEEE,
2009, pp. 21–25.

[20] Y. Shen, Q. Liu, and W. Guo, “Obstacle-avoiding rectilinear steiner minimum
tree construction based on discrete particle swarm optimization,” in Natural
Computation (ICNC), 2011 Seventh International Conference on, vol. 4. IEEE,
2011, pp. 2179–2183.

[21] R. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,”
in Proceedings of the Sixth International Symposium on Micro Machine and
Human Science, 1995. MHS’95. Ieee, 1995, pp. 39–43.

[22] T. Huang and E. Young, “An exact algorithm for the construction of rectilinear
steiner minimum trees among complex obstacles,” in Design Automation
Conference (DAC), 2011 48th ACM/EDAC/IEEE. IEEE, 2011, pp. 164–169.

[23] C. Lee, “An algorithm for path connections and its applications,” Electronic
Computers, IRE Transactions on, no. 3, pp. 346–365, 1961.

[24] J. Soukup, “Fast maze router,” in Proceedings of the 15th Design Automation
Conference. IEEE Press, 1978, pp. 100–102.

[25] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony
of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics,
Part B: Cybernetics, vol. 26, no. 1, pp. 29–41, 1996.

[26] S. Das and S. Gosavi, “An ant colony approach for the steiner tree problem,”
in In: Proc. of Genetic and Evolutionary Computing Conference. Citeseer,
2002.

[27] Y. Hu, T. Jing, X. Hong, Z. Feng, X. Hu, and G. Yan, “An-oarsman: obstacleavoiding
routing tree construction with good length performance,” in Asia and South Pacific Design Automation Conference, 2005. Proceedings of the ASPDAC 2005., vol. 1. IEEE, 2005, pp. 7–12.

[28] Y. Shi, T. Jing, L. He, Z. Feng, and X. Hong, “Cdctree: novel obstacle-avoiding
routing tree construction based on current driven circuit model,” in Proceedings
of the 2006 Asia and South Pacific Design Automation Conference. IEEE Press,
2006, pp. 630–635.

[29] T. Lengauer, Combinatorial algorithms for integrated circuit layout. John
Wiley & Sons, Inc., 1990.

[30] Y. Shi, P. Mesa, H. Yu, and L. He, “Circuit simulation based obstacle-aware
steiner routing,” in Proceedings of the 43rd annual Design Automation Conference.
ACM, 2006, pp. 385–388.

[31] M. Hanan, “On steiner’s problem with rectilinear distance,” SIAM Journal on
Applied Mathematics, vol. 14, no. 2, pp. 255–265, 1966.