In my work at Mentor Graphics, I have applied computational geometry algorithms and concepts on several occasions. In each case, the degree of success has been directly proportional to the ease of obtaining reliable, easy-to-use software.

Delaunay triangulations have proved useful in two different contexts. In one, thermal data in the plane needed to be interpolated. The computational geometers at Mentor Graphics (Nimish Shah and I) knew that the Delaunay triangulation is a good choice for linear interpolation of sampled data. We obtained Steve Fortune's Delaunay code from the Net and easily plugged it in. In the second case, existing code at Mentor Graphics computed Euclidean minimum spanning trees extremely inefficiently. The biggest part of the inefficiency arose because the original programmer did not realize that there are easily computable, linear-size supergraphs of the MST (the Delaunay triangulation, for one). Plugging in Delaunay code speeds up the computation substantially.

I have applied an algorithm for computing a non-crossing matching of
red and blue points (Hershberger and Suri, *BIT*, 32:249-267,
1992) to a problem called *breakout routing*. In this problem, a
component on a printed circuit board has a set of *pins* that
connect to the top layer of the circuit board. In order to reach
other layers, the pins must be connected to a set of *vias* by
disjoint, properly spaced wires in the top layer of the circuit board.
The approach we took to the problem is to select a set of via
locations, then compute a matching between pins and via sites, and
finally route each pin-via pair in the matching. For this approach to
succeed, the matching must be realizable by planar, non-crossing
routing. We get a good first approximation to this constraint by
choosing the matching to consist of non-crossing segments; this can be
done efficiently with the Hershberger-Suri algorithm. Mentor Graphics
has applied for a patent on the application of non-crossing matching
to breakout routing.

Robustness is a third area of potential application. A design tool under development at Mentor Graphics needs to represent arrangements of curves and line segments. It is not possible to write robust software for this problem without some understanding of the numerical issues and degeneracy issues involved. In general, Mentor's programmers do not have the necessary expertise, nor have they been able to obtain code that encapsulates it.

In the first of these examples, publicly available software made it easy to apply a computational geometry algorithm. In the second example, I had to implement the geometric algorithm before I could use it; this is not something that can be expected of the casual user. In the third case, software does not seem to be available; solving the problem requires more geometric expertise than most programmers can muster.

Thu May 9 13:12:40 PDT 1996