變形偶角編織法－－即時超大型積體佈線資料結構技術

Abstract

隅角編織法（Corner stitching）是一種處理即時超大型積體佈線的資料結構。由於 隅角編織法只能處理非常簡單的幾何圖形之模式，即圖形的邊均垂直或水平的長方形 圖形；因此使得隅角編織法雖然簡單有效率但卻不具實用性。 因此本篇論文提出一種隅角編織法的改良版：變形隅角編織法（Degenerate Corner Stitching ）。變形隅角編織法不但能處理任意多邊形而且保持隅角編織法的優良特 性。變形隅角編織法的演算法之計算複雜度與隅角編織法相同。而所需付出之代價只 是須多出一些儲存空間以儲存非長方形圖形之坐標資料。