### ALGORITHMIC GEOMETRY AND MESH GENERATION

####
Math 579 Section 002, also offered as: ECE 595 Section 006

New Time/Place: T 18:00-20:00, Humanities 428, or a warmer room around the corner

University of New Mexico

Instructor: Scott A. Mitchell

No class Sept 28 - attend the
cubit tutorial instead.

No class Oct 5 - balloon fiesta

This webpage
http://www.cs.sandia.gov/~samitch/unm_math_579/index.html

#### Resources

txt files
Computational_Geometry

topics

references, namely books

links

others
links, browsable

#### Homework

rtf files
General instructions

week 1 (due 31 Aug)

week 2 (due 9 Sept)
use this picture:
tetrahedral_ordering.jpg

set 3 (due 13 or 20 October)
you can use these old course notes:
duality_notes0.jpg ,
duality_notes1.jpg ,
duality_notes2.jpg

Turn in homework in class or email it to me
samitch@sandia.gov

#### Papers

Simulation of Simplicity for degenerate points

##### Guaranteed Quality Meshes

Chew website - Guaranteed Quality Triangular Meshes
Chew paper - Guaranteed Quality Triangular Meshes
Ruppert - local feature size definition
BernEppsteinGilbert, quadtree triangulating for points sets
Labelle_thesis Tetrahedral meshes using point lattices (reminiscint of octrees, in that the lattices may be graded, but without the bookkeeping of octree geometric edges and faces). This is a a more modern treatment of my thesis topic, by one of Shewchuck's students. The student is no longer in mesh generation. Deals with point lattices structures that may be familiar to chemists such as body-centered cubic, face centered cubic.
Sliver Exudation external link to pdf of paper
Quality mesh generation in three dimensions" link to my thesis
##### Hex-mesh duality

hex mesh existence via duality
Geode template includes duality structure for tets refined into hexes.

##### Flipping and triangulation updating for moving points

CGAL 3d Triangulations package includes Triangulations are build incrementally and can be modified by... displacements ... of vertices''
Edelsbrunner and N. R. Shah. Incremental topological flipping works for regular triangulations. Algorithmica, 15:223-241, 1996. regular is what we've been calling the weighted DT.
Point Location. Olivier Devillers, Sylvain Pion, and Monique Teillaud. Walking in a triangulation. Internat. J. Found. Comput. Sci., 13:181-199, 2002. How to find the location of a point in a triangulation, that is, which triangle contains it so you know the local region to consider flipping.
Computational Geometry- from theory to practice, From linear objects to curved objects page 8 describes some practical choices of how to implement this. Walks with a few random decisions tends to be best.
Devillers. The Delaunay hierarchy. Internat. J. Found. Comput. Sci., 13:163-180, 2002" Talks about how to save some information for faster point lookup later.
Point removal, using symbolic perturbation to resolve degeneracies. This is the most expensive operation when updating a triangulation, and flips are the cheapest. From CGAL we have:
Olivier Devillers and Monique Teillaud. Perturbations and vertex removal in a 3D Delaunay triangulation. In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 313-319, 2003.
and
Olivier Devillers and Monique Teillaud. Perturbations and vertex removal in Delaunay and regular 3D triangulations. Research Report 5968, INRIA, 2006.
Point movement.

State of the Art: Updating Delaunay Triangulations for Moving Points is a survey of various techniques,

An empirical comparison of techniques for updating Delaunay triangulations
Includes molecular simulation in 3d as the motivating example.

Leonidas Guibas, Menelaos Karaveles, and Daniel Russel. A computational framework for handling motion. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments, pages 129-141, 2004.

CGAL Kinetic Data Structures
The Kinetic Data Structure has been added to CGAL but is not used for relocationfor DT and power DT. The authors state that the following procedure is used instead: (1) insert point at new position;
(2) remove vertex at old position, leaving it disconnected;
(3) updating the info related to the disconnected vertex with the info of the inserted vertex, neighborhood (adjacent cells) and coordinates; (4) delete the vertex at the new position.

Kinetic Data Structures handbook by Guibas et al.

Pedro Machado Manhaes de Castro. Practical Ways to Accelerate Delaunay Triangulations. These de doctorat en sciences, Universite de Nice-Sophia Antipolis, France, 2010.
This describes general combinatorial operations, bibliography of several nice papers on this subject. May be what's in CGAL.

Russel thesis: Kinetic Data Structures in Practice

Delaunay Triangulations for Moving Points

and
Shewchuck's Star splaying: an algorithm for repairing delaunay triangulations and convex hulls That is flip-based and consequently fast.

Additional contact info is on my homepage.

Back to Scott's homepage