Mesh Generation: Open Problems (original) (raw)

If we are given n points in space, the Delaunay triangulation of which has t tetrahedra, how quickly can we find that triangulation?Chan, Snoeyink and Yap have an algorithm with running time O((n + t) log2 t), but this does not quite match the known lower bound of Omega(n log t + t).

Some more practical problems from Mac (meaning, a solution would likely involve an actual working system, although one might imagine theoretical results in these areas):

1. Hex meshing with quality approaching that which is producable by hand - i.e., by region decomposition controlled by an expert.
2. Intelligent meshing of features (if you tell the CAD system to put a certain type of feature on your object, that information should be used by the mesher).
3. Fast remeshing after a local change.
4. Mesh smoothing for high order elements with curved boundaries.
5. Problem dependent, black box meshing, in which the whole process of selecting a mesh type, performing mesh generation, applying a numerical algorithm, etc is automatically performed given some specification of the problem to be solved.
6. Decomposition into "nice" 2-1/2D regions (generalized cylinders, meeting parallel to each other; one could then apply a planar mesh algorithm to the cylinder cross-section and cut horizontally to get a good 3D mesh).

David Eppstein,Theory Group,Dept. Information & Computer Science,UC Irvine.
Last update: