Not for Sale

• #### Conclusion and References 16-16

The important lesson learned is that symbolic manipulation systems can be used to transform physics, as presented in a textbook, to a running FORTRAN program. The higher conceptual level allows small groups to write, in a few weeks, codes that previously required long periods of time and person-years of effort. It should also allow one to retarget codes more easily to a new architecture. In the past, there was a single model of computation, the von Neumann model. Each new generation of computer, with its increased speed, caused all programs to execute faster. Today, as parallel architectures evolve, we can no longer expect a program coded for one architecture to automatically execute on a newer machine with a different parallel architecture. Recoding promises to be a major impediment, particularly if the time to recode an application is several years and thus comparable to the lifetime of a given machine architecture. Moving to a higher conceptual level of programming will become a necessity.

### Triangulations

As our work on modeling and simulation progressed to fluids and other branches of physics, a need for meshes arose. In two dimensions, we faced the problem of triangulating a planar region, making sure that no triangles had small angles. Triangles with small angles are undesirable in that they lead to larger error in certain iterations. A method developed by Paul Chew was very effective and had the advantage that it provided guaranteed lower bounds on the size of angles in the triangulation (Bern and Eppstein, 1992). The method is based on Delaunay triangulations.

The method developed by Chew is to start with a set of points with no two points closer than one unit. A triangle is formed from each set of three points that defines a circle not containing any additional points. Such a triangulation is called a Delaunay triangulation ( Figure 9). If the radius of any circle formed by three points of a Delaunay triangulation was greater than one unit, Chew added a point at the center of the circle and repeated the process of creating a Delaunay triangulation. Note that the point at the center of the circle is at least one unit away from any other point, and thus that property is preserved. The process is repeated until we have a Delaunay triangulation with no large circles (radius greater than one) and no two vertices closer than one.

At this point we have a Delaunay triangulation in which no triangle has any angle less than 30°. To

FIGURE 9 Delaunay triangulation argument.

The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001