General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Trudy Inst. Mat. i Mekh. UrO RAN:

Personal entry:
Save password
Forgotten password?

Trudy Inst. Mat. i Mekh. UrO RAN, 2014, Volume 20, Number 3, Pages 291–308 (Mi timm1101)  

This article is cited in 8 scientific papers (total in 8 papers)

Optimization of the Hausdorff distance between sets in Euclidean space

V. N. Ushakova, A. S. Lakhtinb, P. D. Lebedeva

a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences
b Yeltsin Ural Federal University

Abstract: Set approximation problems play an important role in many research areas; for example, approximation problems for solvability sets and reachable sets of control systems are intensively studied in differential game theory and optimal control theory. In N. N. Krasovskii and A. I. Subbotin's investigations devoted to positional differential games, one of the key problems was the problem of identification of solvability sets, which are maximal stable bridges. This problem can be solved exactly in rare cases only; in most cases, the question of the approximate calculation of solvability sets arises. In papers by A. B. Kurzhanskii and F. L. Chernousko and their colleagues, reachable sets were approximated by ellipsoids and parallelepipeds.
In the present paper, we consider problems in which it is required to approximate a given set by arbitrary polytopes. Two sets, polytopes $A$ and $B$, are given in Euclidean space. It is required to find a position of the polytopes that provides a minimum Hausdorff distance between them. Though the statement of the problem is geometric, methods of convex and nonsmooth analyze are used for its investigation.
One of the approaches to dealing with planar sets in control theory is their approximation by families of disks of equal radii. A basic component of constructing such families is a best $n$-net and its generalizations, which were described, in particular, by A. L. Garkavi. The authors designed an algorithm for constructing best nets based on decomposing a given set into subsets and calculating their Chebyshev centers. Qualitative estimates for the deviation of sets from their best $n$-nets as $n$ grows to infinity were given in the general case by A. N. Kolmogorov. We derive a numerical estimate for the Hausdorff deviation of one class of sets. Examples of constructing of the best $n$-nets are given.

Keywords: Hausdorff distance, polygon, best $n$-net, disk cover.

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

English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2015, 291, suppl. 1, 222–238

Bibliographic databases:

UDC: 517.977

Citation: V. N. Ushakov, A. S. Lakhtin, P. D. Lebedev, “Optimization of the Hausdorff distance between sets in Euclidean space”, Trudy Inst. Mat. i Mekh. UrO RAN, 20, no. 3, 2014, 291–308; Proc. Steklov Inst. Math. (Suppl.), 291, suppl. 1 (2015), 222–238

Citation in format AMSBIB
\by V.~N.~Ushakov, A.~S.~Lakhtin, P.~D.~Lebedev
\paper Optimization of the Hausdorff distance between sets in Euclidean space
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2014
\vol 20
\issue 3
\pages 291--308
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2015
\vol 291
\issue , suppl. 1
\pages 222--238

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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, P. D. Lebedev, “Algorithms for the construction of an optimal cover for sets in three-dimensional Euclidean space”, Proc. Steklov Inst. Math. (Suppl.), 293, suppl. 1 (2016), 225–237  mathnet  crossref  mathscinet  isi  elib
    2. V. V. Gorokhovik, M. A. Trofimovich, “Geometricheskie i analiticheskie kharakteristiki polozhitelno odnorodnykh funktsii”, Tr. In-ta matem., 23:1 (2015), 27–54  mathnet
    3. V. N. Ushakov, P. D. Lebedev, “Algoritmy optimalnogo pokrytiya mnozhestv na ploskosti $\mathbb{R}^2$”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 26:2 (2016), 258–270  mathnet  crossref  mathscinet  elib
    4. V. N. Ushakov, P. D. Lebedev, “Iteratsionnye metody minimizatsii khausdorfova rasstoyaniya mezhdu podvizhnymi mnogougolnikami”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 27:1 (2017), 86–97  mathnet  crossref  elib
    5. A. L. Kazakov, P. D. Lebedev, “Algorithms for constructing optimal $n$-networks in metric spaces”, Autom. Remote Control, 78:7 (2017), 1290–1301  mathnet  crossref  mathscinet  isi  elib
    6. V. N. Ushakov, P. D. Lebedev, N. G. Lavrov, “Algoritmy postroeniya optimalnykh upakovok v ellipsy”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 10:3 (2017), 67–79  mathnet  crossref  elib
    7. Dmitry I. Danilov, Alexey S. Lakhtin, “Optimization of the algorithm for determining the Hausdorff distance for convex polygons”, Ural Math. J., 4:1 (2018), 14–23  mathnet  crossref  mathscinet
    8. A. R. Alimov, I. G. Tsar'kov, “Chebyshev centres, Jung constants, and their applications”, Russian Math. Surveys, 74:5 (2019), 775–849  mathnet  crossref  crossref  mathscinet  adsnasa  isi
  • Trudy Instituta Matematiki i Mekhaniki UrO RAN
    Number of views:
    This page:403
    Full text:113
    First page:14

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