-
Context:
-
Mesh generation consists in subdividing complex objects into simplices
(triangles in 2D, tetrahedra in 3D etc). This is a mandatory step for
solving partial differential equations in numerical simulations.
Though mesh generation is a well understood in dimension two or three,
very little work has been devoted to the problem in higher dimensions.
This is however important when considering time-dependent phenomena
and deforming objects, conveniently represented in 4-dimensional
time--space, or when working in 6-dimensional phase space for nuclear
physics simulations (where a particle is represented by its position
and its velocity), or when working with high dimensional data as is
common in computer vision and machine learning.
-
Description:
-
The present Phd project aims at extending mesh generation based on
Delaunay refinement to higher dimensions. Delaunay refinement has
proven to be a well-founded and extremely versatile paradigm for
meshing 3-dimensional complex domains. The Geometrica project team of
INRIA took the lead on this approach and has developped very efficient
and robust codes that are now available in the open source CGAL
library (www.cgal.org). It is expected that the approach will be
successfully extended and proved useful in higher dimensions.
Two main issues have to be faced. The first one, often referred to as
the curse of dimensionality, is related to the fact that the
complexity of most geometric structures, like polytopes or simplicial
complexes, grows exponentially with the dimension. As a consequence,
the time-complexity of meshing algorithms is a major concern.
The second issue is related to the quality of the mesh which has a
direct impact on the precision and robustness of the
simulation. Delaunay refinement alone cannot remove all badly shaped
simplices and it is a hard task to remove them, especially as the
dimension increases. Although techniques have been proposed to remove
bad simplices, they are up to now, rather complicated and inefficient.
Another aspect of mesh optimization is to be able to take into account
anisotropic phenomena so as to optimize the ratio complexity/accuracy
of the simulation. An example to be studied in detail will be the
simulation of the plasma in the heart of Iter, the futur fusion based
nuclear reactor, which requires highly anisotropic meshes.
-
Bibliography:
-
- Geometry and topology for mesh generation, by Herbert Edelsbrunner
Cambridge University Press, 2001.
- Generating well-shaped d-dimensional Delaunay meshes, Li, Xiang-Yang.
Theoretical Computer Science, 2003, 296(1),pages 145-165.
- Incremental construction of the Delaunay graph in medium dimension.
Jean-Daniel Boissonnat, Olivier Devillers, and Samuel Hornus.
In Proc. 25th Annual Symposium on Computational Geometry, pages 208-216, 2009.
- Locally uniform anisotropic meshing,
J-D. Boissonnat, C. Wormser and M. Yvinec.
Proceedings of the twenty-fourth annual symposium on Computational Geometry, 2008, pages 270-277.
|
