Publication Details




Parallel Guaranteed Quality Planar Delaunay Mesh Generation by Concurrent Point Insertion


Andrey Chernikov and Nikos Chrisochoides.


Published in 14th Annual Fall Workshop on Computational Geometry, Cambridge, MA, November, 2004




We develop a theoretical framework for constructing parallel guaranteed quality Delaunay planar meshes using commercial o-the shelf software (COTS). We call two points Delaunay-independent if they can be inserted concurrently without destroying the conformity and Delaunay properties of the mesh. First, we present a sufficient condition of Delaunay-independence. It is based on the distance between points, can be verified very efficiently and used in practice. Second, we show that a simple block mesh decomposition can be utilized in order to guarantee a-priori Delaunay-independence of points in certain regions. Third, we derive an expression which relates three mesh quality and size parameters that allow to conduct the preprocessing step of our approach using a sequential Delaunay refinement algorithm. We conclude with our current work in progress that includes extending the presented approach to generate nonuniform graded meshes.




  [PDF]          [BibTex] 



[Return to Publication List]