A theoretically optimal and practically fast algorithm for VLSI geometrical design rule verification

An optimal algorithm for the minimum space/width checking problem is presented. This algorithm searches the plane in both directions without sorting input data in both directions, keeps the theoretically optimal time and space complexity, and runs fast. It runs in O(n log n) time with O(n/sup 0.5/) main memory space, where n is the number of vertices of the patterns. Although the authors deal only with rectilinear regions as input data, it is easy to extend the algorithm to handle regions with diagonal edges.<>