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