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.

Bibliographie

[1] V.\;A. Klyachin, “Modified Delaunay empty sphere condition in the problem of approximation of the gradient”, Izvestiya: Mathematics, 80:3 (2016), 95–102 | DOI | MR | Zbl

[2] V.\;A. Klyachin, “On a multidimensional analogue of the Schwarz example”, Izvestiya: Mathematics, 76:4 (2012), 41–48 | DOI | MR | Zbl

[3] V.\;A. Klyachin, A.\;A. Shirokiy, “The Delaunay triangulation for multidimensional surfaces and its approximative properties”, Russian Mathematics, 2012, no. 1, 31–39 | Zbl

[4] A.\;V. Skvortsov, N.\;S. Mirza, Algorithms of triangulations design and analisys, Izd-vo Tom. un-ta, Tomsk, 2006, 168 pp.

[5] B.\;N. Delaunay, “Sur la sphere vide. A la memoire de Georges Voronoi”, Izvestiya AN SSSR, 1934, no. 6, 793–800

[6] J.\;R. Shewchuk, What is a good linear finite element? Interpolation, conditioning, anisotropy, and quality measures, preprint, Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, 2002, 66 pp. | MR