Geodesic
Optimization of the Hausdorff distance between sets in Euclidean space
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 3, pp. 291-308

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : Hausdorff distance, polygon
Keywords: best $n$-net, disk cover. 
@article{TIMM_2014_20_3_a19,
     author = {V. N. Ushakov and A. S. Lakhtin and P. D. Lebedev},
     title = {Optimization of the {Hausdorff} distance between sets in {Euclidean} space},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {291--308},
     publisher = {mathdoc},
     volume = {20},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2014_20_3_a19/}
}
TY  - JOUR
AU  - V. N. Ushakov
AU  - A. S. Lakhtin
AU  - P. D. Lebedev
TI  - Optimization of the Hausdorff distance between sets in Euclidean space
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2014
SP  - 291
EP  - 308
VL  - 20
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2014_20_3_a19/
LA  - ru
ID  - TIMM_2014_20_3_a19
ER  - 
%0 Journal Article
%A V. N. Ushakov
%A A. S. Lakhtin
%A P. D. Lebedev
%T Optimization of the Hausdorff distance between sets in Euclidean space
%J Trudy Instituta matematiki i mehaniki
%D 2014
%P 291-308
%V 20
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2014_20_3_a19/
%G ru
%F TIMM_2014_20_3_a19
V. N. Ushakov; A. S. Lakhtin; P. D. Lebedev. Optimization of the Hausdorff distance between sets in Euclidean space. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 3, pp. 291-308. http://geodesic.mathdoc.fr/item/TIMM_2014_20_3_a19/