An O(nlogm) algorithm for VLSI design rule checking

摘要

This paper describes a new variant of the segment tree approach for VLSI design rule checking. The best known algorithms to date for flat VLSI design rule checking require O(nlogn) expected time and O(√n) expected space, where n is the total number of edges on a mask layer of the chip. We present a new algorithm that can run in O(nlogm) expected time, where m is the maximum feature size on a particular mask layer. Since the maximum feature size must be bounded by the height of a chip, i.e. m ≤ O(√n), the new algorithm is adaptively more efficient than O(nlogn). For layers such as diffusion or contact windows where the maximum feature size is independent of chip size, i.e. m = O(1), the new algorithm runs in O(n) expected time, a definite improvement. The improved time efficiency is achieved without sacrificing O(√n) expected space complexity.