Each student in the class, including auditors,
is expected to present one paper on triangulations or mesh generation.
The presentation is a requirement for a passing grade.
(If you are taking the course S/U, it is the only requirement.)
Please choose one or more of the following dates
and one or more of the following papers,
and send me email to let me know.
I'll assign you the first date and paper on your list that aren't taken.
I'll send you a reply to let you know whether
you got the date and paper you asked for.
Please have a date assigned to you no later than February 27.
You are welcome to choose only a date now,
and put off choosing the paper (or change your choice)
until two weeks before your date.
However, papers are assigned firstcome firstserved.
You are also welcome to choose a relevant paper not on this list
(and you are encouraged to do so if it is helpful to your own research),
but please provide me with a copy two weeks before your presentation.
There is time for two student presentations on each available date.
When a student chooses a date and paper,
I'll put their name next to each below,
so that you'll know which dates and papers were already taken
last time I updated this page.
You must make an appointment with me to give a practice talk at
least one week before your inclass talk, so that I have an opportunity
to suggest improvements.
(Note that I usually don't come to campus on Tuesdays.)
Also see my advice on
Giving an
Academic Talk.
Your presentation should take 25 to 40 minutes.
Don't feel you must present everything in a paper;
rather, concentrate on presenting the most interesting or important parts.
Give theoretical proofs only if you think you can present them
well in the time allotted.
You may use a laptop, an overhead projector, or (if you dare)
the whiteboard. Many of the authors have posted their own talk slides
to the web, or will send them to you if you ask them.
You are encouraged to use them as a source of figures, but you should make
your own slides—don't try to give someone else's talk.
Dates
Up to two students may present on each of the following dates.
Monday, April 7 
Jessica Schoen, Nuttapong Chentanez.
Wednesday, April 9 
Ilya Landa.
Wednesday, April 16 
Jimmy Andrews, Darsh Ranjan.
Wednesday, April 23 
James Hamlin, Peter Bogatsky.
Wednesday, April 30 
Meng Yu, Siyu Song.
Wednesday, May 7 
Hagen Wille, Dino Bellugi.
Papers
Optimal Triangulations

Marshall Bern, Scott Mitchell, and Jim Ruppert,
LinearSize Nonobtuse Triangulation of Polygons,
Discrete & Computational Geometry 14:411428, 1995.
Gnuzipped PostScript (93k) or
PDF (280k).
How to triangulate a polygon so that no angle is larger than 90^{o}.
(There is no bound on the smallest angle.)
For a brief description of this result, see Bern and Eppstein, pages 2930.
There is also a version of this algorithm that creates quadrilateral meshes
(further down this page).

Matthew T. Dickerson, J. Mark Keil, and Mark H. Montague,
A Large Subgraph of the Minimum Weight Triangulation,
Discrete & Computational Geometry 18(3):289304, October 1997.
PDF (214k).
The minimum weight triangulation (MWT) is the triangulation of a point set
whose total edge length is shortest.
For many years, it was not known whether there is a polynomial algorithm for
the MWT. Recently, the problem was proven to be NPhard;
but for most point sets of modest size,
the MWT can be computed by techniques discussed here.
Incidentally, the cubictime algorithm this paper mentions for finding the MWT
of a polygon (rather than a point set, which is NPcomplete)
is Klincsek's algorithm (see Bern and Eppstein, pages 1718).
I have an accompanying video (on videotape):
Patrice Belleville, Mark Keil, Michael McAllister, and Jack Snoeyink,
On Computing Edges That Are In All MinimumWeight Triangulations,
Fifth Annual Video Review of Computational Geometry, ACM, May 1996.
See also
Proceedings of the Twelfth Annual Symposium on Computation Geometry
(Pittsburgh, Pennsylvania), pages V7V8, ACM, May 1996.
Delaunay Triangular Mesh Generation

Steven Pav and Noel Walkington,
Delaunay Refinement by Corner Lopping,
14th International Meshing Roundtable (San Diego, California),
pages 165181, September 2005.
PDF (1,373k).
Many realworld domains have curved boundaries.
This paper extends Ruppert's algorithm to deal with curves.
(Unfortunately, the electronic version of this paper is missing two figures.
Ask me for photocopies.)

Hale Erten and Alper Üngör,
Triangulations with Locally Optimal Steiner Points,
Symposium on Geometry Processing 2007 (Barcelona, Spain),
pages 143152, July 2007.
PDF (615k).
This paper modifies Ruppert's algorithm by inserting new vertices
not just at triangle circumcircles, but at locations that are less likely
to create new bad triangles.
The meshes Erten and Üngör generate have fewer triangles
than Ruppert's meshes (for a fixed bound on the minimum angle),
or can be refined until their worst angles are about 42^{o}
(in practice—there's no guarantee).

Benoît Hudson, Gary Miller, and Todd Phillips,
Sparse Voronoi Refinement,
15th International Meshing Roundtable (Birmingham, Alabama),
pages 339356, September 2006.
PDF (226k).
In three dimensions, the Delaunay triangulation of n points may
have Θ(n^{2}) tetrahedra.
If you run Delaunay refinement on such a domain, the new vertices will
eventually bring the complexity down to something reasonable;
but meanwhile you will suffer a quadratic hit in your running time.
Sparse Voronoi refinement guarantees a nearoptimal running time by
interleaving refinement with insertion of the input vertices
(rather than constructing a Delaunay triangulation of the input before
beginning to refine).
QuadtreeBased Triangular Mesh Generation

Marshall Bern, David Eppstein, and John R. Gilbert,
Provably Good Mesh Generation,
Journal of Computer and System Sciences 48(3):384409, June 1994.
Gnuzipped PostScript (151k) or
PDF (341k).
This classic paper gives the first sizeoptimal guaranteedquality
meshing algorithm (from before Ruppert invented his algorithm).
It's based on quadtrees.
For a brief description of this result, see Bern and Eppstein, pages 2225.

Friedhelm Neugebauer and Ralf Diekmann,
Improved Mesh Generation: Not Simple But Good,
Fifth International Meshing Roundtable (Pittsburgh, Pennsylvania),
pages 257270, October 1996.
Gnuzipped PostScript (84k) or
PDF (251k).
An improvement to the Bern, Eppstein, and Gilbert algorithm
that uses a rhomboidal quadtree.
Tetrahedral Mesh Generation and Improvement

Pierre Alliez, David CohenSteiner, Mariette Yvinec, and Mathieu Desbrun,
Variational Tetrahedral Meshing,
ACM Transactions on Graphics 24(3):617625, 2005.
Special issue on Proceedings of SIGGRAPH 2005.
PDF (778k).
An example of tetrahedral mesh generation from the graphics literature.
Their algorithm iterates between a smoothing operation that
minimizes a function (the volume between the lifted triangulation
on the parabolic lifting map and the paraboloid itself) and recomputing
the Delaunay triangulation (which minimizes the same function).
In other words, it alternates between moving the vertices and
changing their connectivity.
The authors seem to get good meshes in practice, with few slivers
(though they do not report the worst tetrahedra; instead they report
distributions of quality).
Warning: I know two people who have independently implemented this algorithm,
and both report that recovering good sliverfree boundaries is much harder
than the authors indicate.
Nuttapong Chentanez.

SiuWing Cheng, Tamal Krishna Dey, Herbert Edelsbrunner, Michael A. Facello,
and ShangHua Teng, Sliver Exudation,
Journal of the ACM 47(5):883904, September 2000.
Gnuzipped PostScript (120k) or
PDF (294k).
If you present this paper, I suggest you include figures and results from
Herbert Edelsbrunner and Damrong Guoy,
An Experimental Study of Sliver Exudation,
Engineering with Computers 18:229240, 2002.
PDF (790k).
A provably good mesh improvement algorithm that uses flips
to remove slivers from a Delaunay mesh.
The algorithm keeps the triangulation weighted Delaunay at all times.
Unfortunately, the provable bounds are so weak (probably less than
a millionth of a degree for the dihedral angles) that the authors don't bother
to compute them; but Edelsbrunner and Guoy show that the algorithm is
much better in practice than the theory can guarantee
(though not as good as Freitag and OllivierGooch's heuristic approach).
Quadrilateral Mesh Generation and Improvement

Marshall Bern and David Eppstein,
Quadrilateral Meshing by Circle Packing,
Sixth International Meshing Roundtable (Park City, Utah),
pages 719, October 1997.
Gnuzipped PostScript (267k) or
PDF (139k).
An elegant algorithm for creating quadrilateral meshes with no angles larger
than 120^{o}.
(There is no bound on the smallest angle.)

Paul Kinney,
CleanUp: Improving Quadrilateral Finite Element Meshes,
Sixth International Meshing Roundtable (Park City, Utah),
pages 449461, October 1997.
Gnuzipped PostScript (40k) or
PDF (36k).
How to apply topological transformations to improve an existing
quadrilateral mesh.
James Hamlin.

Kenji Shimada, JiaHuei Liao, and Takayuki Itoh,
Quadrilateral Meshing with Directionality Control through the
Packing of Square Cells,
Seventh International Meshing Roundtable (Dearborn, Michigan),
pages 6175, October 1998.
Gnuzipped PostScript (627k) or
PDF (723k).
Bubble meshing for quadrilateral meshes.
Whereas the iterative nature of bubble meshing makes it uncompetitively slow
for (isotropic) triangular meshing, it's much more attractive for
the tougher problem of quadrilateral meshing.
Hexahedral Mesh Generation and Improvement

Matthew L. Staten, Steven J. Owen, and Ted D. Blacker,
Unconstrained Paving & Plastering: Progress Update,
15th International Meshing Roundtable (Birmingham, Alabama),
pages 469486, September 2006.
PDF (3,647k).
For additional details and pictures, you might also want to look at their
earlier installment,
Matthew L. Staten, Steven J. Owen, and Ted D. Blacker,
Unconstrained Paving & Plastering: A New Idea for All Hexahedral
Mesh Generation,
14th International Meshing Roundtable (San Diego, California),
pages 399416, September 2005.
PDF (2,176k).
Plastering is an advancingfront method for hexahedral mesh generation,
and the threedimensional equivalent of paving.
Unstructured hexahedral mesh generation is an extremely hard problem.
Although it is far from completely solved, this paper will give you a sense
of the state of the art and why the problem is so hard.

Marshall Bern, David Eppstein, and Jeff Erickson,
Flipping Cubical Meshes,
Engineering with Computers 18(3):173187, October 2002.
PDF (218k).
This paper describes flips that replace one set of hexahedral elements
with another set, and likewise for quadrilateral flips.
It also has a discussion (mainly of theoretical interest) of the circumstances
under which you can guarantee that a flip will create hexahedra with planar
faces.

Ted Blacker,
The Cooper Tool,
Fifth International Meshing Roundtable (Pittsburgh, Pennsylvania),
pages 1329, October 1996.
Gnuzipped PostScript (1,236k) or
PDF (1,895k).
The most common technique for generating a hexahedral mesh is sweeping
a quadrilateral mesh along the third axis.
This technique only works well if the object being meshed is nicely structured.
Here's a relatively sophisticated discussion of how to make sweeping work
on complicated shapes.

Robert W. Leland, Darryl J. Melander, Ray W. Meyers, Scott A. Mitchell,
and Timothy J. Tautges,
The Geode Algorithm: Combining Hex/Tet Plastering,
Dicing and Transition Elements
for Automatic, AllHex Mesh Generation,
Seventh International Meshing Roundtable (Dearborn, Michigan),
pages 515521, October 1998.
Gnuzipped PostScript (206k) or
PDF (203k).
An interesting realworld paper that gives you an idea what kinds of
clever tricks and compromises people make
when they write industrial meshing software.

Alla Sheffer, Michal Etzion, Ari Rappoport, and Michel Bercovier,
Hexahedral Mesh Generation using the Embedded Voronoi Graph,
Seventh International Meshing Roundtable (Dearborn, Michigan),
pages 347364, October 1998.
Gnuzipped PostScript (2,155k) or
PDF (2,972k).
The authors use a structure similar to the medial axis to decompose
a domain into polyhedra for which simple sweep algorithms can create
a hexahedral mesh.

Timothy J. Tautges, Ted Blacker, and Scott Mitchell,
The Whisker Weaving Algorithm: A ConnectivityBased Method for Constructing
AllHexahedral Finite Element Meshes.
Gnuzipped PostScript (155k) or
PDF (155k).
You might also find it useful to consult the more detailed description
of the spatial twist continuum in
Peter Murdoch, Steven Benzley, Ted Blacker, and Scott A. Mitchell,
The Spatial Twist Continuum Captures the Global Connectivity of an
AllHexahedral Finite Element Mesh
Gnuzipped PostScript (33k) or
PDF (38k).
Whisker weaving is a topological approach to
unstructured hexahedral mesh generation of general shapes.
Although it has not yielded a practical mesh generation algorithm
(because it neglects geometry too much), these papers are still
a great introduction to the topological difficulties of hexahedral meshing,
and remain a mustread for anyone trying to understand the problem.
Ask me for a companion paper that describes the Spatial Twist Continuum (STC)
in greater detail; it has some helpful figures.
(In fact, you might wind up mostly just presenting the STC paper.)

Matthias MüllerHannemann,
Shelling Hexahedral Complexes for Mesh Generation,
Journal of Graph Algorithms and Applications 5(5):5991, 2001.
PDF (736k).
Another topological approach to hexahedral mesh generation.
MüllerHannemann avoids some of the problems that whisker weaving has
by first repairing the surface mesh to remove selfintersecting cycles in
the dual.
The volume mesh generation step works by performing transformations
that remove the remaining cycles from the surface mesh dual.
The hexahedra are determined by running this cycleremoval process in reverse.
Moving Meshes

David Cardoze, Alexandre Cunha, Gary L. Miller, Todd Phillips, and
Noel Walkington,
A BézierBased Approach to Unstructured Moving Meshes,
Twentieth Annual Symposium on Computational Geometry (Brooklyn, New York),
pages 310319, June 2004.
PDF (691k).
This paper uses Bézier triangular elements—elements
with curved edges, modeled by Bsplines—and flips
to maintain a mesh that dynamically changes through time to model blood flow
(while maintaining the boundaries of the red blood cells).
The challenge is to keep the quality of the triangles good as they deform.
Hagen Wille.

Pankaj K. Agarwal, Bardia Sadri, Hai Yu,
Untangling Triangulations through Local Explorations,
to appear in
TwentyFourth Annual Symposium on Computational Geometry
(College Park, Maryland), June 2008.
Draft PDF (242k).
When the vertices of a triangular mesh move during a Lagrangian finite element
simulation, some of the triangles may become inverted,
meaning that their orientations are reversed,
because there are folds in the fabric of the mesh.
In this circumstance, you cannot count on the flip algorithm to correct
the tangled mesh, so the authors instead locally retriangulate small portions
of the mesh.
Starting with one inverted seed triangle, this paper shows how
to find a minimal set of triangles (including the seed) that
can be removed and replaced solely by triangles that are not inverted.
Note that this is the submitted version (taken from Bardia Sadri's web page);
the final conference version is not available yet.
Anisotropic Meshing

Frank Bossen and Paul Heckbert,
A Pliant Method for Anisotropic Mesh Generation,
Fifth International Meshing Roundtable (Pittsburgh, Pennsylvania),
pages 6374, October 1996.
Gnuzipped PostScript (572k) or
PDF (450k).
Slides from a related talk by Paul are also available in
Gnuzipped PostScript (313k) or
PDF (353k).
Some applications require meshes in which the elements are anisotropic,
meaning that they are deliberately skinny, because you can interpolate
a function with anisotropic curvature more accurately by using properly
aligned skinny triangles.
This paper uses an iterative particlebased method to distribute vertices
to create an anisotropic triangular mesh.
Although iterative methods are relatively slow (compared to Delaunay
or advancing front methods), their flexibility makes them easy to apply
to problems like anisotropy.
If you present this paper, consider reading the paper below as well.

Kenji Shimada,
Anisotropic Triangular Meshing of Parametric Surfaces via
Close Packing of Ellipsoidal Bubbles,
Sixth International Meshing Roundtable (Park City, Utah),
pages 375390, October 1997.
Gnuzipped PostScript (521k) or
PDF (629k).
Bubble meshing uses an iterative particlebased method to
distribute vertices.
See the comments for the paper above; they all apply here too.
If you present this paper, consider reading the paper above as well.

François Labelle and Jonathan Richard Shewchuk,
Anisotropic Voronoi Diagrams and
GuaranteedQuality Anisotropic Mesh Generation,
Proceedings of the Nineteenth Annual Symposium on
Computational Geometry (San Diego, California), pages 191200,
Association for Computing Machinery, June 2003.
PostScript (910k) or
PDF (284k).
Slides from a related
talk (PDF, 1,301k) are also available.
This paper puts anisotropic mesh generation on firm theoretical ground.
The skewed elements are generated by a provably good
Voronoi refinement algorithm
that incrementally updates an anisotropic Voronoi diagram,
wherein each site has its own distorted distance metric.
Jessica Schoen.
Isosurface Extraction and Surface Meshing

JeanDaniel Boissonnat and Steve Oudot,
Provably Good Surface Sampling and Approximation,
Symposium on Geometry Processing (Aachen, Germany), pages 918, June 2003.
PDF (technical report version, 1,728k).
This paper and
an earlier paper
by Paul Chew
created the foundations for provably good Delaunay mesh generation on surfaces.
If you present this paper, don't get lost in the details of the theorems;
focus on the highlevel ideas.

Scott Schaefer and Joe Warren,
Dual Marching Cubes: Primal Contouring of Dual Grids,
Computer Graphics Forum 24(2):195201, 2005.
PDF (1,037k).
A clever isosurface extraction method that can often extract
thin features without using a fine grid.
It works in two steps.
The first step uses a dual octree method, similar to dual contouring,
to create a second background grid that places corners in
thin features.
The second step uses a primal method, similar to marching cubes,
over the second background grid to triangulate the isosurface.
Jimmy Andrews.
Surface Reconstruction

Brian Curless and Marc Levoy,
A Volumetric Method for Building Complex Models from Range Images,
Computer Graphics (SIGGRAPH '96 Proceedings), pages 303312, 1996.
Gnuzipped PostScript (766k) or
PDF (270k).
Slides from their talk are also available in
Gnuzipped PostScript (4,024k) or
PDF (581k).
One of the earliest and bestknown papers on
building surfaces to fit point data.
Takes advantage of the properties of laser range finders,
such as your knowledge of the direction from which each point was scanned.
It has no guaranteed bounds,
but it's extremely fast and works well in practice.

Christian Früh, Siddharth Jain, and Avideh Zakhor,
Data Processing Algorithms for Generating Textured 3D Building Facade
Meshes from Laser Scans and Camera Images,
International Journal of Computer Vision 61(2):159184,
February 2005.
PDF (5,778k).
These folks drove a truck around Berkeley with a couple of lasers and a camera
attached, then created a realtime walkthrough of the storefronts!
And you thought Britney Spears defined cool.
Ilya Landa.

Yutaka Ohtake, Alexander Belyaev, Marc Alexa, Greg Turk, and HansPeter Seidel,
MultiLevel Partition of Unity Implicits,
ACM Transactions on Graphics 22(3):463470, July 2003.
Special issue on Proceedings of SIGGRAPH 2003.
The input is a cloud of points where each point has a normal vector attached,
understood to be normal to the true surface.
The output is an isosurface that approximates the original surface from which
the points were sampled.
A triangulated surface can then be extracted from the isosurface by methods
like marching cubes or dual contouring—or the isosurface can be
rendered directly.
The idea is elegant, but I suspect this method does not deal with noisy data
as well as the other papers here.

Michael M. Kazhdan, Matthew Bolitho, and Hugues Hoppe,
Poisson Surface Reconstruction,
Symposium on Geometry Processing 2006 (Cagliari, Italy), pages 6170,
June 2006.
PDF (12,654k).
Like the paper above, this paper presents a method for computing an isosurface
from a cloud of points with attached normals.
This method is much more resistant to noise (which laser scans usually
have lots of), but is correspondingly more complicated.

Z. Kaufman, M. Engelberg, and M. Zager,
Fecal
Fistula: A Late Complication of Marlex Mesh Repair,
Diseases of the Colon & Rectum 24(7):543544, October 1981.
A mesh repair paper that advocates
the use of extraperitoneal meshes to close burst abdominal manifolds.
Although both extraperitoneal and intraperitoneal meshes offer
guarantees of watertightness and high quality, intraperitoneal meshes may
become incorporated into the splenic flexure and cause a fistula,
a condition wherein the digestive manifold has a genus one greater than
it should have. The authors depict an example in which this caused the
“discharge of fecal content from the left subcostal region.”
Triangulating Multiple Planar Cross Sections

Chandrajit L. Bajaj, Edward J. Coyle, and KwunNan Lin,
Surface and 3D Triangular Meshes from Planar Cross Sections,
Fifth International Meshing Roundtable (Pittsburgh, Pennsylvania),
pages 169178, October 1996.
Gnuzipped PostScript (123k) or
PDF (223k).
How to reconstruct the surface or volume of a solid, given only
planar cross sections of it.
Discrete Differential Geometry

Mark Meyer, Mathieu Desbrun, Peter Schröder, and Alan H. Barr,
Discrete DifferentialGeometry Operators for Triangulated 2Manifolds,
pages 3558 of Visualization and Mathematics III,
HansChristian Hege and Konrad Polthier (editors),
SpringerVerlag, Berlin, 2003.
PDF (5,660k).
A central theme of the CalTech graphics group is the development and use
of discrete versions of the ideas that form differential geometry.
This survey describes how continuous ideas like normal vectors, curvature,
and differential operators can be discretized for use with
surface triangulations.

Timothy D. Gatzke and Cindy M. Grimm,
Estimating Curvature on Triangular Meshes,
International Journal of Shape Modeling 12(1):129, June 2006.
PDF (400k).
A survey and empirical comparison of discrete curvature operators and
the circumstances under which they fail.
Mesh Simplification

Hugues Hoppe,
ViewDependent Refinement of Progressive Meshes,
Computer Graphics (SIGGRAPH '97 Proceedings), pages 189198, August 1997.
Gnuzipped PostScript (3,891k) or
PDF (601k).
Slides from Hugues'
talk (PDF, 5,051k) are also available.
Hoppe's paper Progressive Meshes is the secondmost cited SIGGRAPH
paper ever (after the marching cubes paper).
Whereas the first paper focused on sending geometry over slow transmission
lines, this followup paper applies the idea for fast rendering.
Progressively simplified triangular surfaces can be rendered at
different levels of detail, trading off resolution for rendering speed.
For example, faraway objects can be rendered with fewer triangles.
Moreover, the resolution can vary within a single mesh—for example,
finer triangles can be used at the silhouettes.
Peter Bogatsky.

Michael Garland and Paul Heckbert,
Fast Triangular Approximation of Terrains and Height Fields,
manuscript, May 1997.
Gnuzipped PostScript (1,818k) or
PDF (690k).
For applications in Geographical Information Systems and terrain databases,
it is useful to be able to simplify triangulated terrains
for fast rendering.
The most efficient triangulation is not necessarily Delaunay, but rather has
“datadependent” triangles chosen to best represent the terrain.
Computer Graphics

Olga Sorkine, Daniel CohenOr, Rony Goldenthal, and Dani Lischinski,
BoundedDistortion Piecewise Mesh Parameterization,
Proceedings of the Conference on Visualization '02 (Boston, Massachusetts),
pages 355362, 2002.
PDF (3,522k).
An algorithm for mesh parametrization (see above)
that simultaneously cuts the surface mesh and computes how it is distorted.
The authors can guarantee bounds on the distortion, because in any circumstance
where it is not feasible to keep the distortion small, they cut more edges.

Pierre Alliez, Giuliana Ucelli, Craig Gotsman, and Marco Attene,
Recent Advances in Remeshing of Surfaces,
Chapter 2 of Shape Analysis and Structuring,
Leila de Floriani and Michela Spagnuolo (editors),
Springer, Berlin, November 2007.
PDF (14,644k).
A survey of methods to remesh a surface to improve the spacing of its vertices
and the quality of its triangles for applications like rendering,
texture mapping, editing, and creating control meshes for subdivision surfaces.

Fakir S. Nooruddin and Greg Turk,
Simplification and Repair of Polygonal Meshes Using Volumetric
Techniques,
IEEE Transactions on Visualization and Computer Graphics 9(2):191205,
AprilJune 2003.
PDF (14,745k).
The geometric models produced for computer graphics are usually
“polygon soup”—full of holes and cracks and
selfintersecting polygons.
This paper describes a way of repairing these messes and producing
clean, watertight manifolds.
Siyu Song.

Aaron W. F. Lee, David Dobkin, Wim Sweldens, and Peter Schröder,
Multiresolution Mesh Morphing,
Computer Graphics (SIGGRAPH '99 Proceedings), (Los Angeles, California),
pages 343350, August 1999.
PDF (42,270k).
How to morph one triangular surface mesh into another.

Mathieu Desbrun, Mark Meyer, Peter Schröder, and Alan H. Barr,
Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow,
Computer Graphics (SIGGRAPH '99 Proceedings) (Los Angeles, California),
pages 317324, August 1999.
PDF (1,735k).
When you generalize the idea of mesh smoothing to a surface triangulation,
things can go wrong—for instance, the surface could shrink inward.
Here's a sophisticated method for smoothing noisy surfaces well.
Darsh Ranjan.
Mesh Compression

Jarek Rossignac,
Edgebreaker: Connectivity Compression for Triangle Meshes,
Technical Report GITGVU9835, GVU Center, Georgia Institute of Technology,
October 1998.
Gnuzipped PostScript (125k) or
PDF (173k).
A method for compression of triangular meshes for
rapid transmission over slow communication lines.
Delaunay Triangulations

Guy E. Blelloch, Gary L. Miller, and Dafna Talmor,
Developing a Practical ProjectionBased Parallel Delaunay Algorithm,
Proceedings of the Twelfth Annual Symposium on Computation Geometry
(Philadelphia, Pennsylvania), pages 186195, ACM, May 1996.
Gnuzipped PostScript (226k) or
PDF (518k).
Slides from Dafna's talk are also available in
Gnuzipped PostScript (303k) or
PDF (637k).
This is the only parallel Delaunay triangulation algorithm I am aware of
that is good in both theory and practice.

Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, and Jack Snoeyink,
Streaming Computation of Delaunay Triangulations,
ACM Transactions on Graphics 25(3):10491056, July 2006.
Special issue on Proceedings of SIGGRAPH 2006.
PDF (9,175k).
Streaming is a method for outofcore computation that makes it possible
to compute Delaunay triangulations of billions of points
on an ordinary laptop computer.
See also the
video
(your choice of iPod, QT/mpeg4, DivX, MW/avi, MW/mpg1, or orig mov) from
the Proceedings of the Fifteenth Video Review of Computational Geometry.

Peter Su and Robert L. Scot Drysdale,
A Comparison of Sequential Delaunay Triangulation Algorithms,
Proceedings of the Eleventh Annual Symposium on Computational Geometry
(Vancouver, British Columbia, Canada), pages 6170, ACM, June 1995.
Gnuzipped PostScript (93k) or
PDF (229k).
A comparison of the speed of
twodimensional Delaunay triangulation algorithms.
Unfortunately, they don't have an implementation of the divideandconquer
algorithm, which is probably the fastest algorithm in practice.
You might also want to look at Chapter 2 of Peter Su's dissertation
for additional figures and algorithmic details.
Gnuzipped PostScript (383k) or
PDF (892k).

Olivier Devillers,
Improved Incremental Randomized Delaunay Triangulation,
Proceedings of the Fourteenth Annual Symposium on Computation Geometry
(Minneapolis, Minnesota), pages 106115, ACM, June 1998.
Gnuzipped PostScript (113k) or
PDF (195k).
Also check out the technical report by the same name
which has bigger figures (better for presenting)
and perhaps more useful information.
Gnuzipped PostScript (218k) or
PDF (346k).
This paper describes an interesting randomized dynamic point location method
for incremental Delaunay triangulation.
It works with vertex deletions, as well as insertions.
Good in both theory and practice.
I find the analysis of the running time for point location to be
beautifully elegant.

Herbert Edelsbrunner and Tiow Seng Tan,
An Upper Bound for Conforming Delaunay Triangulations,
Discrete & Computational Geometry 10(2):197213, August 1993.
Gnuzipped PostScript (67k) or
PDF (248k).
The algorithm that achieves the best known bound for the number of
Steiner points needed to create a Delaunay triangulation
that conforms to a specified PSLG.
For a brief description of this result, see Bern and Eppstein, pages 3738.