David Eppstein - Publications

Int. Meshing Roundtable

• Quadrilateral meshing by circle packing.
  M. Bern and D. Eppstein.
  2nd CGC Worksh. Computational Geometry, Durham, North Carolina, 1997.
  6th Int. Meshing Roundtable, Park City, Utah, 1997, pp. 7–19.
  arXiv:cs.CG/9908016.
  Int. J. Comp. Geom. & Appl. 10 (4): 347–360, 2000.

  We use circle-packing methods to generate quadrilateral meshes for polygonal domains, with guaranteed bounds both on the quality and the number of elements. We show that these methods can generate meshes of several types:

  1. The elements form the cells of a Voronoi diagram,
  2. The elements each have two opposite 90 degree angles,
  3. All elements are kites, or
  4. All angles are at most 120 degrees.

  In each case the total number of elements is \(O(n)\). The 120-degree bound is optimal; if a simply-connected region has all angles at least 120 degrees, any mesh of that region has a 120 degree angle.

• Flipping cubical meshes.
  M. Bern D. Eppstein, and J. Erickson.
  arXiv:cs.CG/0108020.
  10th Int. Meshing Roundtable, Newport Beach, 2001, pp. 19–29.
  Engineering with Computers 18 (3): 173–187, 2002.

  We examine flips in which a set of mesh cells connected in a similar pattern to a subset of faces of a cube or hypercube is replaced by cells in the pattern of the complementary subset. We show that certain flip types preserve geometric realizability of a mesh, and use this to study the question of whether every topologically meshable domain is geometrically meshable. We also study flip graph connectivity, and prove that the flip graph of quadrilateral meshes has exactly two connected components.

  Note that the Meshing Roundtable version was by Bern and Eppstein. Erickson was added as a co-author during the revisions for the journal version.

  (Slides)

• Global optimization of mesh quality.
  D. Eppstein.
  Tutorial at 10th Int. Meshing Roundtable, Newport Beach, 2001.

  Delaunay triangulation has been a staple of triangular mesh generation for a long time. Why? As well as being simple, fast, and visually pleasing, Delaunay triangulations can be shown to be optimal for various measures of mesh quality; for instance, they avoid sharp angles to the maximum extent possible. We review these and other results on construction of meshes that optimize given quality measures, including recent work on postprocessing tetrahedral meshes to eliminate slivers.

  (slides)

• Diamond-kite meshes: adaptive quadrilateral meshing and orthogonal circle packing.
  D. Eppstein.
  arXiv:1207.5082.
  21st International Meshing Round Table, San Jose, California, 2012, pp. 261–277.
  Engineering with Computers 30 (2): 223–235 (special issue for the 21st Int. Meshing Roundtable), 2014.

  We describe a recursive subdivision of the plane into quadrilaterals in the form of rhombi and kites with 60, 90, and 120 degree angles. The vertices of the resulting quadrilateral mesh form the centers of a set of circles that cross orthogonally for every two adjacent vertices, and it has many other properties that are important in finite element meshing.

  (Slides)