Next: Geometric tools, teaching, and Up: Geometric Tools Previous: Introduction

# Applications of computational geometry

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.

Next: Geometric tools, teaching, and Up: Geometric Tools Previous: Introduction

John Hershberger
Thu May 9 13:12:40 PDT 1996