An O(nlogm) Algorithm for VLSI Design Rule Checking.

This memo 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(sqrt n) expected space, where n is to total number of edges on a mask layer of the chip. In this paper, 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