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 September 28.
You are welcome to choose only a date now,
and put off choosing the paper until up to a week 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 you must provide me with a copy one week before your presentation.
You may change your mind about what paper to present up to a week
before your presentation, but please let me know as early as possible.
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.
Your presentation should take 25 to 30 minutes.
Don't feel you must present everything in a paper;
rather, concentrate on presenting the most interesting or important parts.
Give theoretical proofs (if any) only if you think you can present them
well in the time allotted.
Please use the overhead projector for your presentation if possible.
I will try to make blank writeon transparencies available,
if I can lay my hands on enough of them.
(If I can't, you'll have to buy your own.
Ditto for photocopies of figures in the papers.)
Dates
Up to two students may present on each of the following dates.
Thursday, October 7 
Jason Riedy, Andy Neureuther.
Thursday, October 21  Jae Kim, Borlin Shyu.
Tuesday, November 2 
Dan Simkins, Jordan Smith.
Thursday, November 4 
Michael Downes, Ganping Sun.
Tuesday, November 9 
Tolga Goktekin, Okan Arikan.
Thursday, November 11 
François Labelle, Maryann Simmons.
Tuesday, November 16  Steve Chien, Jane Wang.
Thursday, November 18 
Yan Zhuang, Chris Tchou.
Tuesday, November 23  Tzicker Chiueh.
Papers
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.
PostScript.
Slides from Dafna's
talk (PostScript) are also available.
François Labelle.
This is the only parallel Delaunay triangulation algorithm I am aware of
that is good in both theory and practice.

Olivier Devillers,
Improved Incremental Randomized Delaunay Triangulation,
Proceedings of the Fourteenth Annual Symposium on Computation Geometry
(Minneapolis, Minnesota), pages 106115, ACM, June 1998.
PostScript.
Also check out the
technical report (PostScript)
by the same name, which has bigger figures (better for photocopying)
and perhaps more useful information. Jae Kim.
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.
You may want to consider implementing this paper as your "something extra"
for Project I.

Herbert Edelsbrunner and Tiow Seng Tan,
An Upper Bound for Conforming Delaunay Triangulations,
Discrete & Computational Geometry 10(2):197213, August 1993.
PostScript.
This is the paper that gives an 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.

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.
PostScript.
You might also want to look at Chapter 2 of
Peter Su's dissertation (PostScript)
for additional figures and algorithmic details.
Maryann Simmons.
This is the best extant comparison of the speed of
twodimensional Delaunay triangulation algorithms.
Optimal Triangulations

Marshall Bern, Herbert Edelsbrunner, David Eppstein, Scott Mitchell,
and Tiow Seng Tan,
Edge Insertion for Optimal Triangulations,
Discrete & Computational Geometry 10:4765, 1993.
PostScript.
This paper shows how to construct a triangulation that
minimizes the maximum angle
(whereas the Delaunay triangulation maximizes the minimum angle).
You will need to be selective about which parts of this paper to present.
Ideally, try to convey an intuition of why this algorithm
can minimize the maximum angle.
For a brief description of this result, see Bern and Eppstein, pages 1417.

Marshall Bern, Scott Mitchell, and Jim Ruppert,
LinearSize Nonobtuse Triangulation of Polygons,
Discrete & Computational Geometry 14:411428, 1995.
PostScript.
How to triangulate a polygon so that no angle is larger than 90 degrees.
For a brief description of this result, see Bern and Eppstein, pages 2930.

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.
The minimum weight triangulation (MWT) is the triangulation of a vertex set
whose total edge length is shortest.
It is not known whether there is a polynomial algorithm for the MWT,
nor whether the problem is NPhard.
However, in many cases, the MWT can be computed by techniques discussed here.
The paper mentions a cubictime algorithm for finding the MWT of a polygon
(rather than a point set, for which no polynomial algorithm is known).
This algorithm can be found in Bern and Eppstein, pages 1718.
Triangulating Multiple Planar Cross Sections
Bubble Meshing

Frank Bossen and Paul Heckbert,
A Pliant Method for Anisotropic Mesh Generation,
Fifth International Meshing Roundtable (Pittsburgh, Pennsylvania),
pages 6374, October 1996.
PostScript.
Slides from a related
talk (PostScript) by Paul are also available.

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.
PostScript. Ganping Sun.
QuadtreeBased 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.
PostScript.
This classic paper gives the first sizeoptimal guaranteedquality
meshing 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.
PostScript.
An improvement to the Bern, Eppstein, and Gilbert algorithm
that uses a rhomboidal quadtree.
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.
PostScript.
An algorithm for creating quadrilateral meshes with no angles larger than
120 degrees.

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

Steven J. Owen, Matthew L. Staten, Scott A. Canann, and Sunil Saigal,
Advancing Front Quadrilateral Meshing Using Triangle Transformations,
Seventh International Meshing Roundtable (Dearborn, Michigan),
pages 409428, October 1998.
PostScript. Dan Simkins.
This appears to be a particularly good paper on quadrilateral mesh generation.

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.
PostScript.
Bubble meshing ideas applied to quadrilateral meshes.
Hexahedral Mesh Generation

Ted Blacker,
The Cooper Tool,
Fifth International Meshing Roundtable (Pittsburgh, Pennsylvania),
pages 1329, October 1996.
PostScript. Steve Chien.
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.
PostScript. Borlin Shyu.
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.
PostScript.
A polyhedral decomposition approach to hexahedral mesh generation.

Timothy J. Tautges, Ted Blacker, and Scott Mitchell,
The Whisker Weaving Algorithm: A ConnectivityBased Method for Constructing
AllHexahedral Finite Element Meshes.
PostScript.
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
(PostScript).
Jason Riedy.
Whisker weaving is the most sophisticated approach to
unstructured hexahedral mesh generation of general shapes.
It's difficult to understand and implement,
but it's probably going to be the best once the theory is better sorted out.
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.)
Surface Reconstruction
Mesh Simplification

Michael Garland and Paul Heckbert,
Fast Triangular Approximation of Terrains and Height Fields,
manuscript, May 1997.
PostScript. Okan Arikan.
For applications in Geographical Information Systems and terrain databases,
it is useful to be able to simplify triangulated terrains
for coarse or fast rendering.

Michael Garland and Paul Heckbert,
Surface Simplification Using Quadric Error Metrics,
Computer Graphics (SIGGRAPH '97 Proceedings), August 1997.
PostScript.
Slides from their
talk (PDF) are also available.
Andy Neureuther.
Here, we are interested in simplifying general triangulated surfaces
embedded in threedimensional space.
These surfaces may be much more complicated than terrains.

Hugues Hoppe,
ViewDependent Refinement of Progressive Meshes,
Computer Graphics (SIGGRAPH '97 Proceedings), pages 189198, August 1997.
PostScript.
Slides from Hugues'
talk (PDF) are also available.
Tolga Goktekin.
Progressively simplified triangular surfaces can be rendered at
different levels of detail,
depending on how they are viewed.
That way, you can trade off detail and rendering time.

Jovan Popovic and Hugues Hoppe,
Progressive Simplicial Complexes,
Computer Graphics (SIGGRAPH '97 Proceedings), pages 217224, August 1997.
PostScript.
Slides from Hugues'
talk (PDF) are also available.
Michael Downes.
A simplification/compression method that preserves topological,
as well as geometric, information.
Mesh Compression