An O(n log m) algorithm for VLSI design rule checking

摘要

The authors describe 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(n log n) expected time and O( square root n) space, where n is the total number of edges on a mask layer of the chip. The expectation is with respect to a uniform distribution of edges over the chip area. The authors present a new algorithm of O(n log m) expected time complexity, where m is the maximum feature size for a given mask layer. Since m is bounded by the height of a chip, i.e. m=O( square root n), the new algorithm is adaptively more efficient than O(n log n). For layers such as diffusion or contact windows where m is independent of the 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( square root n) space complexity.