Mathematical Physics and Computer Simulation
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mathematical Physics and Computer Simulation:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Mathematical Physics and Computer Simulation, 2017, Volume 20, Issue 3, Pages 6–17
DOI: https://doi.org/10.15688/mpcm.jvolsu.2017.3.1
(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
References:
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.
Funding agency Grant number
Russian Foundation for Basic Research 15-41-02517 р_поволжье_а
Document Type: Article
UDC: 514.142.2+514.174.6
BBC: 32.973.26-018.2
Language: Russian
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
Citation in format AMSBIB
\Bibitem{BolKlySap17}
\by A.~V.~Boluchevskaya, V.~A.~Klyachin, M.~E.~Sapraliev
\paper Estimations of clearance radius for finite subset of a unit ball in ${\mathbb{R}}^{n}$
\jour Mathematical Physics and Computer Simulation
\yr 2017
\vol 20
\issue 3
\pages 6--17
\mathnet{http://mi.mathnet.ru/vvgum179}
\crossref{https://doi.org/10.15688/mpcm.jvolsu.2017.3.1}
Linking options:
  • https://www.mathnet.ru/eng/vvgum179
  • https://www.mathnet.ru/eng/vvgum/v20/i3/p6
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Mathematical Physics and Computer Simulation
    Statistics & downloads:
    Abstract page:203
    Full-text PDF :61
    References:36
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024