+7 (3412) 91 60 92

## Archive of Issues

Russia Yekaterinburg
Year
2017
Volume
27
Issue
1
Pages
86-97
 Section Mathematics Title Iterative methods for minimization of the Hausdorff distance between movable polygons Author(-s) Ushakov V.N.a, Lebedev P.D.a Affiliations Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa Abstract 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. Keywords convex polygon, Hausdorff distance, mininimization, Chebyshev center, directional derivative UDC 514.177.2 MSC 11K55, 28A78 DOI 10.20537/vm170108 Received 26 October 2016 Language Russian Citation Ushakov V.N., Lebedev P.D. Iterative methods for minimization of the Hausdorff distance between movable polygons, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2017, vol. 27, issue 1, pp. 86-97. References Krasovskii N.N. Game problems of dynamics. I, Izv. Akad. Nauk SSSR, Tekh. Kibern., 1969, no. 5, pp. 3-12 (in Russian). Rockafellar R. Vypuklyi analiz (Convex analysis), Moscow: Mir, 1973, 472 p. Hausdorff F. Set theory, Providence, RI: Amer. Math. Soc., 1957. Translated under the title Teoriya mnozhestv, Moscow: Komkniga, 2006. Lakhtin A.S., Ushakov V.N. Minimization of the Hausdorff distance between convex polyhedrons, Journal of Mathematical Sciences, 2005, vol. 126, issue 6, pp. 1553-1560. DOI: 10.1007/s10958-005-0043-0 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, 2015, vol. 291, suppl. 1, pp. S222-S238. DOI: 10.1134/S0081543815090151 Garkavi A.L. On the Chebyshev center and convex hull of a set, Uspekhi Mat. Nauk, 1964, vol. 19, issue 6 (120), pp. 139-145 (in Russian). Pshenichnyi B.N. Vypuklyi analiz i ekstremal'nye zadachi (Convex analysis and extremal problems), Moscow: Nauka, 1980, 320 p. 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, 2015, vol. 48, issue 25, pp. 197-201. DOI: 10.1016/j.ifacol.2015.11.084 Dem'yanov V.F., Vasil'ev L.V. Nedifferentsiruemaya optimizatsiya (Nondifferentiable optimization), Moscow: Nauka, 1981, 384 p. Natanson I.P. Teoriya funktsii veshchestvennoi peremennoi (Theory of functions of a real variable), Moscow: Nauka, 1974, 480 p. 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, 2016, vol. 26, issue 2, pp. 258-270. DOI: 10.20537/vm160212 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. Lebedev P.D., Ushakov V.N. A variant of a metric for unbounded convex sets, Vestn. Yuzhno-Ural. Gos. Univ., Ser. Mat., Mekh., Fiz., 2013, vol. 5, issue 1, pp. 40-49 (in Russian). Full text