Generalized Manhattan path algorithm with applications

摘要: The author presents an efficient algorithm for finding a route interconnecting two terminals of arbitrary polygonal shape in layers. main feature the router to be distinguished from existing grid-free routers is that it can handle large vias. has also considered extension multi-terminal nets and demonstrate native which repeats same path process each constituent terminal. Careful considerations may lead more way such three regions (horizontal vertical routable via acceptable region) are not reconstructed time but updated only around obtained. In order do data structure been devised implement insertions deletions line segments O(log n) time. Based on proposed possible solve practical problem concerned with layout design bipolar LSIs. this case purpose find orthogonal wiring predetermined width between pairs avoiding obstacles >