论文部分内容阅读
网格剖分问题是计算几何中的基本问题，在计算科学领域有广泛的应用.本文首先介绍了二维网格剖分的概念与研究发展，阐述了Delaunay剖分的定义与性质，介绍了几种当下流行的二维Delaunay剖分算法.然后对一个复杂度为O(N2)的原始算法通过引入新的数据结构进行了优化，获得了大约O(N)的时间代价的新算法，同时不增加更高阶的空间代价消耗.一系列的数值试验的结果证实了算法的优越性。