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