|
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
|
|
+7 (3412) 91 60 92
Russian