RUS  ENG
Full version
JOURNALS // Mathematical Physics and Computer Simulation // Archive

Mathematical Physics and Computer Simulation, 2017 Volume 20, Issue 3, Pages 6–17 (Mi vvgum179)

Mathematics

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

A. V. Boluchevskayaa, V. A. Klyachina, M. E. Sapralievb

a Volgograd State University
b Kalmyk State University named after B. B. Gorodovikov

Abstract: 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}$.

Keywords: triangulation, empty sphere condition, Delaunay triangulation, convex set, convex function, convex hull.

UDC: 514.142.2+514.174.6
BBK: 32.973.26-018.2

DOI: 10.15688/mpcm.jvolsu.2017.3.1



© Steklov Math. Inst. of RAS, 2024