Mesh generation and optimal triangulation

Marshall Wayne Bern and David Eppstein
Computing in Euclidean Geometry, Lecture Notes Series on Computing, Ding-Zhu Du and Frank Kwang-Ming Hwang, ed., World Scientific, 1992, pp. 23–90
Computing in Euclidean Geometry, Lecture Notes Series on Computing, Ding-Zhu Du and Frank Kwang-Ming Hwang, ed., World Scientific, 1995, pp. 47–123
Tech. report CSL-92-1, Xerox Palo Alto Research Center, 1992
http://www.ics.uci.edu/~eppstein/pubs/BerEpp-CEG-95.pdf

Cited by:

• Systematic local flip rules are generalized Delaunay rules
• The Delaunay triangulation maximizes the mean inradius
• Numerically robust algorithm for constructing constrained Delaunay triangulation
• Optimal tetrahedralization of the 3d-region “between” a convex polyhedron and a convex polygon
• Selecting heavily covered points
• Automatic mesh generation using the symmetric axis transformation of polygonal domains
• Computational geometry: a retrospective
• Stable finite elements for problems with wild coefficients
• Quality mesh generation in three dimensions
• Mesh generation with provable quality bounds
• Approximating the maxmin-angle covering triangulation
• Refining a triangulation of a planar straight-line graph to eliminate large angles
• Optimal Two-Dimensional Triangulations
• An optimal bound for high-quality conforming triangulations
• Linear-size nonobtuse triangulation of polygons
• Coping with inconsistencies: a new approach to produce quality triangulations of polygonal domains with holes for the finite element method
• Guaranteed-quality mesh generation for curved surfaces
• Optimality of the Delaunay triangulation in $R^d$
• Compatible tetrahedralizations
• The computation of simplicial approximations of implicitly defined two-dimensional manifolds
• Computational geometry column 23
• A Delaunay based numerical method for three dimensions: generation, formulation, and partition
• Printed circuit board simplification: simplifying subdivisions in practice
• Strategies for polyhedral surface decomposition: an experimental study
• Stabbing triangulations by lines in 3D
• A Delaunay refinement algorithm for 2-dimensional mesh generation
• Converting triangulations to quadrangulations
• Quadrangulations of planar sets
• Automatic mesh partitioning
• Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time
• Numerical conformal mapping using cross-ratios and Delaunay triangulation
• Locally-adaptive grid generation using quadtrees
• Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator
• Flipping edges in triangulations
• Partitioning meshes with lines and planes
• A free Lagrange method for gas-dynamics
• Local bisection refinement for $n$-simplicial grids generated by reflection
• Zippered polygon meshes from range images
• Fast separator decomposition for finite element meshes
• Steiner triangulation for isotropic and stretched elements
• Multiple sequence comparison and consistency on multipartite graphs
• An $O(n^2)$ heuristic for Steiner minimal trees in $E^3$
• A framework for advancing front techniques of finite element mesh generation
• Optimal good-aspect-ratio coarsening for unstructured meshes
• The efficient location of neighbors for locally refined $n$-simplicial grids
• Control volume meshes using sphere packing: generation, refinement and coarsening
• Hamiltonian triangulations for fast rendering
• A parallel solution strategy for irregular dynamic problems
• 1-irregular element tessellation in mixed element meshes for the control volume discretization method
• Surface and 3D triangular meshes from planar cross-sections
• The edge-flipping distance of triangulations
• Optimal triangulation problems
• Euclidean Steiner minimal trees, minimum energy configurations, and the embedding problem of weighted graphs in $E^3$
• Generalized unstructured decimation
• Good orders for incremental (re)construction
• Guaranteed-quality Delaunay meshing in 3D
• Minimum strictly-convex quadrangulations of convex polygons
• Computational Geometry: Algorithms and Applications
• Triangulations
• Mesh generation: theory, algorithms, and software
• Numerische simulationen für granulare Medien
• Mesh generation and optimal triangulation in three dimensions
• Mesh refinement via bidirected flows: modeling, complexity, and computational results
• Complexity and modeling aspects of mesh refinement into quadrilaterals
• Solution-based mesh quality for triangular and tetrahedral meshes
• High quality quadrilateral surface meshing without template restrictions: a new approach based on network flow techniques
• Three dimensional Delaunay mesh generation using a modified advancing front approach
• Delaunay Refinement Mesh Generation
• Linear-time reconstruction of Delaunay triangulations with applications
• Improved approximations for minimum cardinality quadrangulations of finite element meshes
• Exploiting domain geometry in analogical route planning
• A large subgraph of the minimum weight triangulation
• Trends and developments in computational geometry
• Decimation of isosurfaces with deformable models
• Fast nested dissection for finite element meshes
• Mesh smoothing using a posteriori error estimates
• Adaptive refinement of unstructured finite-element meshes
• Automatic 3D surface meshing to address today's industrial needs
• Quadtree grid generation: Information handling, boundary fitting and CFD applications
• Flow simulation and high performance computing
• General object reconstruction based on simplex meshes
• A branch-and-cut approach for minimum weight triangulation
• Fully Unstructured Delaunay Mesh Generation Using a Modified Advancing Front Approach for Applications in Technology CAD
• Tools for triangulations and tetrahedralizations and constructing functions defined over them
• Quadrilateral Mesh Generation in Computer-Aided Design
• On the discrete core of quadrilateral mesh refinement
• Mesh generation
• Computational investigations of the optimality of two- and three-dimensional triangulations under several criteria
• Color printer characterization using a computational geometry approach
• Efficient algorithms for Petersen's matching theorem
• Disparity map coding based on adaptive triangular surface modelling
• The natural element method in solid mechanics
• The computation of simplicial approximations of implicitly defined $p$-dimensional manifolds
• Numerical schemes for the Hamilton-Jacobi and level set equations on triangulated domains
• A solution-based triangular and tetrahedral mesh quality indicator
• Minimum convex partition of a polygon with holes by cuts in given directions
• Finite volume methods on Voronoi meshes
• Bayesian image analysis with Markov chain Monte Carlo and coloured continuum triangulation models
• Mesh generation over curved surfaces with explicit control on discretization error
• On box schemes for elliptic variational inequalities
• Empirical design of geometric algorithms
• How to subdivide pyramids, prisms, and hexahedra into tetrahedra
• Hexahedral mesh generation by successive dual cycle elimination
• Strategies for nonobtuse boundary Delaunay triangulations
• Mesh quality: a function of geometry, error estimates, or both?
• A global minimization-based, automatic quadrilateral meshing algorithm
• LEPP-Delaunay algorithm: a robust tool for producing size-optimal quality triangulations
• Generalized LMT-skeleton heuristics for several new classes of optimal triangulations
• Splitting a complex of convex polytopes in any dimension
• Interactive Rendering of Parametric Spline Surfaces
• Combining hierarchical radiosity and discontinuity meshing
• Construction of a human torso model from magnetic resonance images for problems in computational electrocardiography
• Anisotropic mesh generation with particles
• Visual grid quality assessment for 3D unstructured meshes
• Learning the Voronoi centers of a mobile robot's configuration space
• Tetrahedral meshes from planar cross sections
• A sensory uncertainty field model for unknown and non-stationary mobile robot environments
• Survey of polygonal surface simplification algorithms
• Piecewise linear hypersurfaces using the marching cubes algorithm
• On parallel complexity of planar triangulations
• Algorithms and data structures for handling a fully flexible refinement approach in mesh generation
• A parallel algorithm for finding the constrained Voronoi diagram of line segments in the plane
• A monotone finite element scheme for convection-diffusion equations
• Physical vapor-deposited thin hard films on polymers: sample preparation for SEM analysis
• Shape reconstruction from contours using isotopic deformation
• Micromechanical modeling of concrete response under static loading I: Model development and validation
• Mesh generation for application in technology CAD
• Asymptotics for the length of a minimal triangulation on a random sample
• Adaptive finite element analysis of 2-D static and steady-state electromagnetic problems
• A point-placement strategy for conforming Delaunay tetrahedralization
• Finding minimal triangulations of convex 3-polytopes is NP-hard
• Voronoi diagrams
• Polygon decomposition
• Computational topology
• Delaunay triangulation and Voronoi diagrams for Riemannian manifolds
• Quality mesh generation in higher dimensions
• Unstructured mesh generation: Theory, practice, and perspectives
• Minimal simplicial dissections and triangulations of convex 3-polytopes
• Minimal tetrahedralizations of a class of polyhedra
• Enumerating triangulation paths
• Adaptive simplicial grids from cross-sections of monotone complexes
• Structures of triangulations of points
• Shape similarity by homotopic deformation
• A 3D refinement/derefinement algorithm for solving evolution problems
• Local refinement of simplicial grids based on the skeleton
• Minimum number of pieces in a convex partition of a polygonal domain
• Lipschitzian crowded ball packings and Delaunay spheres
• Force-directed methods for smoothing unstructured triangular and tetrahedral meshes
• Force-directed methods for mesh improvement
• The complexity of finding small triangulations of convex 3-polytopes
• Approximate quality mesh generation based on small edge details
• Tessellations of cuboids with Steiner points
• Static and kinetic geometric spanners with applications
• Anisotropic mesh transformations and optimal error control
• Experimental results on quadrangulations of sets of fixed points
• Multigrid Equation Solvers for Large Scale Nonlinear Finite Element Simulations
• Mesh Generation for Technology CAD in Three Dimensions
• LMT-skeleton heuristics for several new classes of optimal triangulations
• Sliver-Free Three-Dimensional Delaunay Mesh Generation
• Multiresolution shape deformations for meshes with dynamic vertex connectivity
• Optimality and integer programming formulations of triangulations in general dimension
• Approximating uniform triangular meshes in polygons
• Optimal triangulations
• On computing new classes of optimal triangulations with angular constraints
• Managing large terrain data sets with a multiresolution structure
• FIST: Fast industrial-strength triangulation of polygons
• Numerical identification of the potential of whisker- and platelet-filled polymers
• Geometry based triangulation of multiple trimmed NURBS surfaces
• Stability and existence of solutions of time-implicit finite volume schemes for viscous nonlinear conservation laws
• Terminal-edges Delaunay (small-angle based) algorithm for the quality triangulation problem
• Accurate integration of surface profile data with quantitative error analysis
• Atomic images – a method for meshing digital images
• Sample shuffling for quality hierarchic surface meshing
• Quality meshing with weighted Delaunay refinement
• Unstructured tetrahedral meshing by an edge-based advancing front method
• Computational geometry - Some easy questions and their recent solutions
• Approximate shape quality mesh generation
• Approximation for minimum triangulations of simplicial convex 3-polytopes
• Tetrahedralization of two nested convex polyhedra
• Multicriteria-optimized triangulations
• Shelling hexahedral complexes for mesh generation
• Constructing differentiable homeomorphisms between isomorphic triangulations
• Diagonal flips in labelled planar triangulations
• Higher order Delaunay triangulations
• Three-dimensional hybrid mesh generation for turbomachinery airfoils
• Triangulations in CGAL
• Delaunay refinement algorithms for triangular mesh generation
• Approximating uniform triangular meshes for spheres
• Spatial embedding of pseudo-triangulations
• Adapting (pseudo)-triangulations with a near-linear number of edge flips
• Quadtree, ray shooting and approximate minimum weight Steiner triangulation
• BSP-assisted constrained tetrahedralization
• Transforming triangulations of polygons on non planar surfaces
• A time efficient Delaunay refinement algorithm
• Volumetric meshes for real-time medical simulations
• Supporting cuts and finite element deformation in interactive surgery simulation
• Free-form shape design using triangulated surfaces
• Grid generation and optimization based on centroidal Voronoi tessellations
• Approximation and Geometric Processing of Digital Images with Adaptive Triangular Meshes
• Optimal tetrahedralizations of some convex polyhedra
• Enumerating triangulations of convex polytopes
• Axisymmetric dynamical models for SAURON and OASIS observations of NGC 3377
• Dynamic capacitated minimum spanning trees
• Generating surface geometry in higher dimensions using local cell tilers
• Optimal Delaunay triangulations
• The long-time behaviour of the thermoconvective flow in a porous medium
• Finite Volume and Finite Volume Element Methods for Nonsymmetric Problems
• Small point sets whose graph of triangulations is not connected (abridged)
• 3d terrain mapping: a stochastic approach
• Multibeam data processing: a detailed algorithm to compute (adaptive) triangulations and potential indicators of data quality
• Multibeam data processing: data reduction, adaptive triangular meshing and comments resulting from Brouns et al. (THJ No. 101, 2001)
• Phase unwrapping with GAMMA ISP
• Quadrilateral meshes for the registration of human brain images
• A new algorithm for generating quadrilateral meshes and its application to FE-based image registration
• On decreased importance of algorithmic strategies in current ACM curricula for graphics & visual computing
• Automatic grid finding in calibration patterns using Delaunay triangulation
• Voxelization of solids using simplicial coverings
• Subdivision Surfaces in Computer Games
• Points and combinatorics
• Orbit determination with very short arcs: admissible regions
• A numerical method for interface tracking
• Edge-constrained marching triangles
• Animationsorientierte Optimierung von Polygonnetzen
• Neue Untersuchungen zur Integration von DGM und DSM mittels Triangulationen zur Berechnung integrierter 2.5D-Landschaftsmodelle
• Konzeption und Implementierung von geometrischen 3D-Datentype
• Surface reconstruction from problem point clouds
• Topology alteration for virtual sculpting using spatial deformation
• Modelling built environments from large range images using adaptive triangular meshes
• Stochastic simulation in surface reconstruction and application to 3D mapping
• Comparison of image-transformation methods used in matching 2d gel electrophoresis images
• A mapping-independent primitive for the triangulation of parametric surfaces
• Direct interface tracking of droplet deformation
• A Delaunay approach to interactive cutting in triangulated surfaces
• Cutting in Deformable Objects
• Precise relative positioning of multiple moving platforms using GPS carrier phase observables
• Delaunay Refinement Algorithms
• From point cloud to surface: the modeling and visualization problem
• Atomic meshes: from seismic images to reservoir simulation
• Robust Surface Reconstruction Strategy for Large Clouds of Points: State of the Art and Concept of Doctoral Thesis
• Energy Minimization Methods for Feature Displacement in Map Generalization
• Information lack localization in architectural laser scanning surveys: the Venice test site
• Schwarz-Christoffel Mapping
• Representation and Detection of Shapes in Images
• Geometric Decompositions and Networks: Approximation Bounds and Algorithms
• Algorithmic problems on proximity and location under metric constraints
• A 2d kinetic triangulation with near-quadratic topological changes
• Connectivity shapes
• Detecting tetrahedralizations of a set of line segments
• Finding a triangular mesh with a constant number of different edge lengths
• Merging range images of arbitrarily shaped objects
• Pseudo-triangulations from surfaces and a novel type of edge flip
• Triangulations and meshes in computational geometry
• Efficient and reliable triangulation of polygons
• Representation and detection of deformable shapes