Geodesic
Iterative algorithms for minimizing the Hausdorff distance between convex polyhedrons
Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 57 (2021), pp. 142-155.

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

The problem of finding the optimal location of moving bodies in three-dimensional Euclidean space is considered. We study the problem of finding such a position for two given polytopes $ A $ and $ B $ at which the Hausdorff distance between them would be minimal. To solve it, the apparatus of convex and nonsmooth analysis is used, as well as methods of computational geometry. Iterative algorithms have been developed and justification has been made for the correctness of their work. A software package has been created, its work is illustrated with specific examples.
Mots-clés : Hausdorff distance
Keywords: minimization, subdifferential, Chebyshev center. 
@article{IIMI_2021_57_a5,
     author = {P. D. Lebedev and A. A. Uspenskii and V. N. Ushakov},
     title = {Iterative algorithms for minimizing the {Hausdorff} distance between convex polyhedrons},
     journal = {Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta},
     pages = {142--155},
     publisher = {mathdoc},
     volume = {57},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIMI_2021_57_a5/}
}
TY  - JOUR
AU  - P. D. Lebedev
AU  - A. A. Uspenskii
AU  - V. N. Ushakov
TI  - Iterative algorithms for minimizing the Hausdorff distance between convex polyhedrons
JO  - Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
PY  - 2021
SP  - 142
EP  - 155
VL  - 57
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IIMI_2021_57_a5/
LA  - ru
ID  - IIMI_2021_57_a5
ER  - 
%0 Journal Article
%A P. D. Lebedev
%A A. A. Uspenskii
%A V. N. Ushakov
%T Iterative algorithms for minimizing the Hausdorff distance between convex polyhedrons
%J Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
%D 2021
%P 142-155
%V 57
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IIMI_2021_57_a5/
%G ru
%F IIMI_2021_57_a5
P. D. Lebedev; A. A. Uspenskii; V. N. Ushakov. Iterative algorithms for minimizing the Hausdorff distance between convex polyhedrons. Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 57 (2021), pp. 142-155. http://geodesic.mathdoc.fr/item/IIMI_2021_57_a5/

[1] E. M. Bronshtein, “Approksimatsiya vypuklykh mnozhestv mnogogrannikami”, Sovremennaya matematika. Fundamentalnye napravleniya, 22, 2007, 5–37

[2] H. Alt, P. Braß, M. Godau, C. Knauer, C. Wenk, “Computing the Hausdorff distance of geometric patterns and shapes”, Discrete and Computational Geometry, Springer, Berlin-Heidelberg, 2003, 65–76 | DOI | MR | Zbl

[3] P. M. Gruber, “Approximation by convex polytopes”, Polytopes: abstract, convex and computational, Springer, Dordrecht, 1994, 173–203 | DOI | MR

[4] D. P. Huttenlocher, G. A. Klanderman, W. J. Rucklidge, “Comparing images using the Hausdorff distance”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 15:9 (1993), 850–863 | DOI

[5] S. Theodoridis, K. Koutroumbas, Pattern recognition, Academic Press, 2006 | DOI | MR | Zbl

[6] V. N. Ushakov, A. S. Lakhtin, P. D. Lebedev, “Optimizatsiya khausdorfova rasstoyaniya mezhdu mnozhestvami v evklidovom prostranstve”, Trudy Instituta matematiki i mekhaniki UrO RAN, 20, no. 3, 2014, 291–308

[7] V. N. Ushakov, P. D. Lebedev, “Iteratsionnye metody minimizatsii khausdorfova rasstoyaniya mezhdu podvizhnymi mnogougolnikami”, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki, 27:1 (2017), 86–97 | DOI | MR | Zbl

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

[9] A. L. Garkavi, “O chebyshevskom tsentre i vypukloi obolochke mnozhestva”, UMN, 19:6(120) (1964), 139–145 | MR | Zbl

[10] B. N. Pshenichnyi, Vypuklyi analiz i ekstremalnye zadachi, Nauka, M., 1980 | MR

[11] R. Rokafellar, Vypuklyi analiz, Mir, M., 1973

[12] D. I. Danilov, A. S. Lakhtin, “Optimization of the algorithm for determining the Hausdorff distance for convex polygons”, Ural Mathematical Journal, 4:1 (2018), 14–23 | DOI | MR | Zbl

[13] N. Z. Shor, Metody minimizatsii nedifferentsiruemykh funktsii i ikh prilozheniya, Naukova dumka, Kiev, 1979

[14] P. K. Belobrov, “K voprosu o chebyshevskom tsentre mnozhestva”, Izvestiya vysshikh uchebnykh zavedenii. Matematika, 1964, no. 1, 3–9 | MR | Zbl

[15] P. D. Lebedev, A. A. Uspenskii, V. N. Ushakov, “Algoritmy minimizatsii khausdorfova otkloneniya vypuklogo kompakta ot nabora podvizhnykh vypuklykh mnogougolnikov”, Chelyabinskii fiziko-matematicheskii zhurnal, 5:2 (2020), 218–232 | DOI | MR

[16] P. D. Lebedev, N. G. Lavrov, “Algoritmy postroeniya optimalnykh upakovok sharov v ellipsoidy”, Izvestiya Instituta matematiki i informatiki Udmurtskogo gosudarstvennogo universiteta, 52 (2018), 59–74 | DOI | MR | Zbl