Estimations of clearance radius for finite subset of a unit ball in ${\mathbb{R}}^{n}$

A. V. Boluchevskaya ; V. A. Klyachin ; M. E. Sapraliev

Matematičeskaâ fizika i kompʹûternoe modelirovanie, Tome 20 (2017) no. 3, pp. 6-17

Résumé

Let $P = \{P_i\}$, $i~=~1,\ldots,N$, be a finite set of points in ${\mathbb{R}}^n$. Consider a classical problem — approximation of derivatives of function $f~\in~C^1({\mathbb{R}}^n)$ using function values at points $P_i$. One method of solving this problem is based on building triangulation $T$ of set $P$. If $p_{i_0}$, $p_{i_1},\ldots,p_{i_n} \in P$ are vertices of simplex $S$ in triangulation $T$ then we may find a function $$ f_S(x) = \langle a, x\rangle + b, $$ such that $$ f(p_{i_k})=f_S(p_{i_k}), \quad k=0,\ldots,n. $$ Then we can approximate gradient $\nabla f(x)$ in points $x \in S$ by gradient of linear function $\nabla f_S(x)$. By $\delta_S(f)$ denote an absolute error of gradient computation $$ \delta_S(f) = \max_{x \in S} |\nabla f(x) - \nabla f_S(x)|. $$ If simplexes diameters are getting smaller then behavior of $\delta_S(f)$ is connected not only with simplexes structure but also with triangulation geometry in whole. Let us remind that triangulation $T$ is called Delaunay triangulation if an empty sphere condition holds: for every simplex $S \in T$ its circumsphere does not contain points of $P$ inside of itself ([4;5]). In paper [3] and partially in paper [6] it was proven that if $n = 2$ and a set of points $P$ is an $\varepsilon$-net then the following estimate is true for Delaunay triangulation of $P$ $$ \max_{S \in T} \delta_S(f) \le C(f) \varepsilon, $$ where constant $C(f)$ depends on the function class. V.A. Klyachin tried to get an analogous result for spaces of dimensions more than 3. But in [2] it was shown that in a multidimensional case an empty sphere condition is not enough for getting a similar estimate. Therefore in [1] a modified empty sphere condition was given. If this modified empty sphere condition holds then the following inequality is true $$ \max_{S \in T} \delta_S(f) \le C(f) \cdot \varepsilon / \eta_{k,n}, $$ where $C(f)$ is a constant depending on the function class, and $\eta_{k,n}$ is defined in the following way. Let $B(x,t)$ be an open ball of radius $t>0$ with a center in $x \in \mathbb{R}^n$. Then $$ \eta_{k,n}=\inf_{q_1,...,q_k\in B(0,1)}\sup_{y_0\in B(0,1)}\{\rho: B(y_0,\rho)\subset B(0,1)\setminus\{q_1,...,q_k\}\}. $$ This paper is devoted to studying $\eta_{k,n}$.

Détail

Mots-clés : triangulation, Delaunay triangulation
Keywords: empty sphere condition, convex set, convex function, convex hull.