OPTIMAL DELAUNAY TRIANGULATIONS
OPTIMAL DELAUNAY TRIANGULATIONS
复制标题
DOI：
--
复制
发表时间：
2004
影响因子：
1.4
通讯作者：
LongChen;Jin-chaoXu
中科院分区：
文献类型：
--
作者：
LongChen;Jin-chaoXu
本文研究了经典意义和广义意义上的Delaunay三角剖分法，以使给定函数的线性插值误差（L^ p范数测量）最小化。经典的Delaunay三角剖分可以被表征为一个最优的三角剖分，最大限度地减少各向同性函数‖x‖^2在所有的三角剖分与一组给定的顶点之间的插值误差。对于更一般的函数，函数相关的Delaunay三角剖分被定义为使该函数的插值误差最小化的最优三角剖分，其构造可以通过简单的提升和投影过程获得。最优Delaunay三角剖分是顶点数相同的所有三角剖分中插值误差最小的三角剖分，即顶点的分布经过优化以使插值误差最小。证明了对于任意给定的凸连续函数存在函数依赖的最优Delaunay三角剖分。在与f相关的最优Delaunay三角剖分上，证明了内部顶点的△↓f可以通过其相邻顶点上的函数值精确恢复。针对实践中难以获得最优Delaunay三角剖分的问题，引入了近最优三角剖分的概念，并给出了三角剖分接近最优的两个充分条件。
The Delaunay triangulation, in both classic and more generalized sense, is studied in this paper for minimizing the linear interpolation error (measure in L^P-norm) for a given function. The classic Delaunay triangulation can then be characterized as an optimal triangulation that minimizes the interpolation error for the isotropic function ‖x‖^2 among all the triangulations with a given set of vertices. For a more general function, a functiondependent Delaunay triangulation is then defined to be an optimal triangulation that minimizes the interpolation error for this function and its construction can be obtained by a simple lifting and projection procedure. The optimal Delaunay triangulation is the one that minimizes the interpolation error among all triangulations with the same number of vertices, i.e. the distribution of vertices are optimized in order to minimize the interpolation error. Such a function-depend entoptimal Delaunay triangulation is proved to exist for any given convex continuous function.On an optimal Delaunay triangulation associated with f, it is proved that △↓f at the interior vertices can be exactly recovered by the function values on its neighboring vertices.Since the optimal Delaunay triangulation is difficult to obtain in practice, the concept of nearly optimal triangulation is introduced and two sufficient conditions are presented for a triangulation to be nearly optimal.