|
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.
Citation:
A. V. Boluchevskaya, V. A. Klyachin, M. E. Sapraliev, “Estimations of clearance radius for finite subset of a unit ball in ${\mathbb{R}}^{n}$”, Mathematical Physics and Computer Simulation, 20:3 (2017), 6–17
Linking options:
https://www.mathnet.ru/eng/vvgum179 https://www.mathnet.ru/eng/vvgum/v20/i3/p6
|
Statistics & downloads: |
Abstract page: | 203 | Full-text PDF : | 61 | References: | 36 |
|