RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Trudy Inst. Mat. i Mekh. UrO RAN:
Year:
Volume:
Issue:
Page:
Find






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


Trudy Inst. Mat. i Mekh. UrO RAN, 2018, Volume 24, Number 1, Pages 223–235 (Mi timm1510)  

This article is cited in 1 scientific paper (total in 1 paper)

An estimate of the Hausdorff distance between a set and its convex hull in Euclidean spaces of small dimension

V. N. Ushakova, A. A. Ershovba

a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
b Chelyabinsk State University

Abstract: We derive estimates for the Hausdorff distance between sets and their convex hulls in finite-dimensional Euclidean spaces with the standard scalar product and the corresponding norm. In the first part of the paper, we consider estimates for $\alpha$-sets. By an $\alpha$-set we mean an arbitrary compact set for which the parameter characterizing the degree of nonconvexity and computed in a certain way equals $\alpha$. In most cases, the parameter $\alpha$ is the maximum possible angle under which the projections to this set are visible from points not belonging to the set. Note that $\alpha$-sets were introduced by V.N. Ushakov for the classification of nonconvex sets according to the degree of their nonconvexity; $\alpha$-sets are used for the description of wavefronts and for the solution of other problems in control theory. We consider $\alpha$-sets only in a two-dimensional space. It is proved that, if $\alpha$ is small, then the corresponding $\alpha$-sets are close to convex sets in the Hausdorff metric. This allows to neglect their nonconvexity and consider such sets convex if it is known that the parameter $\alpha$ is small. The known Shapley-Folkman theorem is often applied in the same way. In the second part of the paper we present some improvements of the estimates from the Shapley-Folkman theorem. The original Shapley-Folkman theorem states that the Minkowski sum of a large number of sets is close in the Hausdorff metric to the convex hull of this sum with respect to the value of the Chebyshev radius of the sum. We consider a particular case when the sum consists of identical terms; i.e., we add some set $M$ to itself. For this case we derive an improved estimate, which is essential for sets in spaces of small dimension. In addition, as in Starr's known corollary, the new estimate admits the following improvement: the Chebyshev radius $R(M)$ on the right-hand side can be replaced by the inner radius $r(M)$ of the set $M$. However, as the dimension of the space grows, the new estimate tends asymptotically to the estimate following immediately from the Shapley-Folkman theorem.

Keywords: $\alpha$-set, Minkowski sum, convex hull, Hausdorff distance.

Funding Agency Grant Number
Russian Foundation for Basic Research 18-31-00018 мол_а


DOI: https://doi.org/10.21538/0134-4889-2018-24-1-223-235

Full text: PDF file (243 kB)
References: PDF file   HTML file

English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2019, 305, suppl. 1, S178–S190

Bibliographic databases:

UDC: 517.977
MSC: 52A27, 52A30
Received: 10.09.2017

Citation: V. N. Ushakov, A. A. Ershov, “An estimate of the Hausdorff distance between a set and its convex hull in Euclidean spaces of small dimension”, Trudy Inst. Mat. i Mekh. UrO RAN, 24, no. 1, 2018, 223–235; Proc. Steklov Inst. Math. (Suppl.), 305, suppl. 1 (2019), S178–S190

Citation in format AMSBIB
\Bibitem{UshErs18}
\by V.~N.~Ushakov, A.~A.~Ershov
\paper An estimate of the Hausdorff distance between a set and its convex hull in Euclidean spaces of small dimension
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2018
\vol 24
\issue 1
\pages 223--235
\mathnet{http://mi.mathnet.ru/timm1510}
\crossref{https://doi.org/10.21538/0134-4889-2018-24-1-223-235}
\elib{http://elibrary.ru/item.asp?id=32604059}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2019
\vol 305
\issue , suppl. 1
\pages S178--S190
\crossref{https://doi.org/10.1134/S0081543819040187}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000436169800019}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85073418811}


Linking options:
  • http://mi.mathnet.ru/eng/timm1510
  • http://mi.mathnet.ru/eng/timm/v24/i1/p223

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. V. N. Ushakov, A. A. Ershov, M. V. Pershakov, “Ob odnom dopolnenii k otsenke L.S. Pontryagina geometricheskoi raznosti mnozhestv na ploskosti”, Izv. IMI UdGU, 54 (2019), 63–73  mathnet  crossref
  • Trudy Instituta Matematiki i Mekhaniki UrO RAN
    Number of views:
    This page:215
    Full text:24
    References:19
    First page:12

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020