An O(n log m) 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(n log n) expected time and PI 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(n log m) 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(n log n). 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 (√n) expected space complexity.