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(√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(√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(√n) space complexity