## VLSI Design

VLSI circuit design involves many levels of abstraction; the most
geometric of these is the physical design level, in which circuits are
represented as (typically) collections of rectangles representing layers
of various materials on a chip. Most of the layout, routing, and verification
problems at this level involve some amount of computational geometry.
At another level of abstraction, simulation of the electronic and
physical properties of a chip involves interesting questions of mesh generation, in which there may be some
advantage to be taken from the fact that the geometry is rectilinear and
planar or nearly planar.
- Academic
CAD sites on the web (primarily VLSI rather than other kinds of CAD).

- Applications of computational geometry.
John Hershberger describes some geometric problems arising in his work
at Mentor graphics including interpolation of thermal data, minimum spanning trees, and breakout
routing in PC board design.

- Carafe -- An
Inductive Fault Analysis Tool for CMOS VLSI Circuits. This VLSI
layout checker finds circuit breaks using a plane sweep
algorithm.

- Computational Geometry Problems in
Integrated Circuit Design and Layout.
Notes by D. Eppstein from a lecture by V. T. Rajan.

- Grid Evolution for Oxidation Simulation. Sahul, McKenna, and Dutton (in this paper from the NUPAD V Conf.) use adaptive quadtree meshes to simulate semiconductor oxidation.

- Level set
methods for following the evolution of interfaces, J. Sethian,
Berkeley. The basic idea is to solve various "advancing front" type problems
such as finding shortest paths around obstacles, by evolving a surface
in one higher dimension that describes the dynamics of the front.
Includes movies and Java applets describing applications to
VLSI design, medical image processing, noise removal from images, and
robot motion planning.

- Topological
Disorder and Conductance Fluctuations in Thin Films. K. Abkemeier
and D. Grier use Delaunay triangulations of randomly perturbed lattice points
to form resistor networks that model the electrical behavior of
amorphous and polycrystalline silicon.

Part of
Geometry in Action,
a collection of applications of computational geometry.

David Eppstein,
Theory Group,
ICS,
UC Irvine.

Semi-automatically
filtered
from a common source file.