US Patent 11176304 Routing a cell of a semiconductor chip

Embodiments are disclosed for routing a cell of a semiconductor chip, the cell being represented by a matrix, encoding first tracks of the cell as columns of the matrix and second tracks of the cell as rows of the matrix, respectively. The method includes performing a sweep operation on the matrix, the sweep operation including generating an index structure indexed by columns of the matrix, the index structure including information on candidate cut shapes that can be placed in a particular column of the matrix. Additionally, the method includes recursively placing cut shapes into the cell based on the index structure, one recursion of the placing including finding a possible cut shape and recursively placing the remaining cut shapes.