University of New Mexico
Math 579 Section 002, also offered as: ECE 595 Section 006
Time/Place: T-Th 18:30-19:45, Humanities 428 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

Resources

General

• computational geometry
• topics
• references, namely books
• links others
• links, browsable

Homework

• 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 Triangular Meshes
  • Chew mesh website at Cornell, and his mesh website there. Also ResearchGate.
  • Chew paper
• Ruppert – local feature size definition
• Bern Eppstein Gilbert, 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 Shewchuk’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

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
  • Shewchuk’s Star splaying: an algorithm for repairing Delaunay triangulations and convex hulls. That is flip-based and consequently fast.