phone +7 (3412) 91 60 92

Archive of Issues

Russia Yekaterinburg
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.
  1. Krasovskii N.N. Game problems of dynamics. I, Izv. Akad. Nauk SSSR, Tekh. Kibern., 1969, no. 5, pp. 3-12 (in Russian).
  2. Rockafellar R. Vypuklyi analiz (Convex analysis), Moscow: Mir, 1973, 472 p.
  3. Hausdorff F. Set theory, Providence, RI: Amer. Math. Soc., 1957. Translated under the title Teoriya mnozhestv, Moscow: Komkniga, 2006.
  4. 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
  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, 2015, vol. 291, suppl. 1, pp. S222-S238. DOI: 10.1134/S0081543815090151
  6. 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).
  7. Pshenichnyi B.N. Vypuklyi analiz i ekstremal'nye zadachi (Convex analysis and extremal problems), Moscow: Nauka, 1980, 320 p.
  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, 2015, vol. 48, issue 25, pp. 197-201. DOI: 10.1016/j.ifacol.2015.11.084
  9. Dem'yanov V.F., Vasil'ev L.V. Nedifferentsiruemaya optimizatsiya (Nondifferentiable optimization), Moscow: Nauka, 1981, 384 p.
  10. Natanson I.P. Teoriya funktsii veshchestvennoi peremennoi (Theory of functions of a real variable), Moscow: Nauka, 1974, 480 p.
  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, 2016, vol. 26, issue 2, pp. 258-270. DOI: 10.20537/vm160212
  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., 2013, vol. 5, issue 1, pp. 40-49 (in Russian).
Full text
<< Previous article
Next article >>