Jonathan Shewchuk's papers

(Meditations at the Edge: Paper & Spirit, Peter and Donna Thomas.)

Jonathan's papers

Most recent:

Aggressive Tetrahedral Mesh Improvement.
Liquid Simulation.
Isosurface Stuffing.
Streaming Delaunay Triangulations.
Raster DEM from Points via TIN Streaming.

Greatest personal satisfaction:

Constrained Delaunay Triangulations, I: Combinatorial Properties.
Isosurface Stuffing.
Guaranteed-Quality Anisotropic Mesh Generation.

If you're in Soda Hall, you'll find copies of most of my papers hanging outside my office (625). Just take the ones you want.

FAR AND AWAY MY MOST POPULAR PAPER is my introduction to the conjugate gradient method. This report is an exercise in trying to make a difficult subject as transparent and easy to understand as humanly possible. It includes sixty-six illustrations and as much intuition as I can provide. How could fifteen lines of pseudocode take fifty pages to explain?

Also available is a set of full-page figures from the paper, which may be printed on transparencies for classroom use.

Jonathan Richard Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, August 1994. Abstract, PostScript (1,716k, 58 pages), PDF (516k, 58 pages), PostScript of classroom figures (1,409k, 37 pages). PDF of classroom figures (394k, 37 pages).

Delaunay Mesh Generation

DELAUNAY REFINEMENT MESH GENERATION ALGORITHMS construct meshes of triangles or tetrahedra (``elements'') that are suitable for applications like interpolation, rendering, terrain databases, geographic information systems, and most demandingly, the solution of partial differential equations by the finite element method. Delaunay refinement algorithms operate by maintaining a Delaunay or constrained Delaunay triangulation which is refined by inserting additional vertices until the mesh meets constraints on element quality and size. These algorithms simultaneously offer theoretical bounds on element quality, edge lengths, and spatial grading of element sizes; the ability to triangulate general straight-line domains (and not just polygons/polyhedra with holes); and truly satisfying performance in practice.

The following papers include theoretical treatments of Delaunay refinement and discussions of the implementation details of my two-dimensional mesh generator and Delaunay triangulator, Triangle, and my three-dimensional mesh generator and Delaunay tetrahedralizer, Pyramid. See the Triangle page for information about what Triangle can do, or to obtain the C source code.