Print

Nardi, Dan J.

Computer Science

2004

M.S.

We describe a new VLSI design tool that locates all occurrences of a specific geometric configuration within a large-scale layout. The device and layout are modeled using half-edge data structures that maintain the topology, geometry, and processing steps of each mask element. Using the plane-sweep algorithm the data structures are refined so that every set of overlapping elements is replaced with a single labeled element. Then a depth-first-search algorithm, using three different heuristics, finds all subgraphs isomorphic to the target. Applications within VLSI design and other domains are discussed.