Geodesic
Iterative methods for minimization of the Hausdorff distance between movable polygons
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 27 (2017) no. 1, pp. 86-97 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of minimizing the Hausdorff distance between two convex polygons is studied. The first polygon is supposed to be able to make any flat motions including parallel transportation and rotation with the center at any point. The second polygon is supposed to be fixed. Iterative algorithms of step-by-step displacements and rotations of the polygon which provide a decrease in the Hausdorff distance between the moving polygon and the fixed polygon are developed and realized in software programs. Some theorems of correctness of the algorithms are proved for a wide range of cases. Geometrical properties of the Chebyshev center of a compact set and differential properties of the function of Euclidean distance to a convex set are used. The possibility of a multiple launch is provided for in the implementation of the software complex for the purpose of identifying the best found position of the polygon. Modeling for several examples is performed.
Mots-clés : convex polygon, Hausdorff distance
Keywords: mininimization, Chebyshev center, directional derivative. 
@article{VUU_2017_27_1_a7,
     author = {V. N. Ushakov and P. D. Lebedev},
     title = {Iterative methods for minimization of the {Hausdorff} distance between movable polygons},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {86--97},
     year = {2017},
     volume = {27},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2017_27_1_a7/}
}
TY  - JOUR
AU  - V. N. Ushakov
AU  - P. D. Lebedev
TI  - Iterative methods for minimization of the Hausdorff distance between movable polygons
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2017
SP  - 86
EP  - 97
VL  - 27
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VUU_2017_27_1_a7/
LA  - ru
ID  - VUU_2017_27_1_a7
ER  - 
%0 Journal Article
%A V. N. Ushakov
%A P. D. Lebedev
%T Iterative methods for minimization of the Hausdorff distance between movable polygons
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2017
%P 86-97
%V 27
%N 1
%U http://geodesic.mathdoc.fr/item/VUU_2017_27_1_a7/
%G ru
%F VUU_2017_27_1_a7
V. N. Ushakov; P. D. Lebedev. Iterative methods for minimization of the Hausdorff distance between movable polygons. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 27 (2017) no. 1, pp. 86-97. http://geodesic.mathdoc.fr/item/VUU_2017_27_1_a7/

[1] Krasovskii N. N., “Game problems of dynamics. I”, Izv. Akad. Nauk SSSR, Tekh. Kibern., 1969, no. 5, 3–12 (in Russian)

[2] Rockafellar R., Convex analysis, Mir, M., 1973, 472 pp. | MR

[3] Hausdorff F., Set theory, Amer. Math. Soc., Providence, RI, 1957 | MR

[4] Lakhtin A. S., Ushakov V. N., “Minimization of the Hausdorff distance between convex polyhedrons”, Journal of Mathematical Sciences, 126:6 (2005), 1553–1560 | DOI | MR | Zbl

[5] Ushakov V. N., Lakhtin A. S., Lebedev P. D., “Optimization of the Hausdorff distance between sets in Euclidean space”, Proceedings of the Steklov Institute of Mathematics, 291, suppl. 1 (2015), S222–S238 | DOI | MR | Zbl

[6] Garkavi A. L., “On the Chebyshev center and convex hull of a set”, Uspekhi Mat. Nauk, 19:6(120) (1964), 139–145 (in Russian) | Zbl

[7] Pshenichnyi B. N., Convex analysis and extremal problems, Nauka, M., 1980, 320 pp.

[8] Ushakov V. N., Lebedev P. D., Tarasyev A. M., Ushakov A. V., “Optimization of the Hausdorff distance between convex polyhedrons in $\mathbf{R}^3$”, IFAC-PapersOnLine, 48:25 (2015), 197–201 | DOI

[9] Dem'yanov V. F., Vasil'ev L. V., Nondifferentiable optimization, Nauka, M., 1981, 384 pp.

[10] Natanson I. P., Theory of functions of a real variable, Nauka, M., 1974, 480 pp.

[11] Ushakov V. N., Lebedev P. D., “Algorithms of optimal set covering on the planar $\mathbb{R}^2$”, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 26:2 (2016), 258–270 | DOI

[12] Lebedev P. D., The program for calculating the optimal coverage of a hemisphere by a set of spherical segments, The certificate of state registration, No 2015661543, 29.10.2015

[13] Lebedev P. D., Ushakov V. N., “A variant of a metric for unbounded convex sets”, Vestn. Yuzhno-Ural. Gos. Univ., Ser. Mat., Mekh., Fiz., 5:1 (2013), 40–49 (in Russian)