Methods of optimization of Hausdorff distance between convex rotating figures

Authors

  • Pavel Lebedev Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, Russia and Ural Federal University named after the first President of Russia B.N. Yeltsin, Yekaterinburg, Russia
  • Vladimir Ushakov Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, Russia

DOI:

https://doi.org/10.2298/YJOR191125027L

Keywords:

Optimization, Hausdorff Distance, Rotation, Chebyshev Centre, One-sided Dirivative

Abstract

We studied the problem of optimizing the Hausdorff distance between two convex polygons. Its minimization is chosen as the criterion of optimality. It is believed that one of the polygons can make arbitrary movements on the plane, including parallel transfer and rotation with the center at any point. The other polygon is considered to be motionless. Iterative algorithms for the phased shift and rotation of the polygon are developed and implemented programmatically, providing a decrease in the Hausdorff distance between it and the fixed polygon. Theorems on the correctness of algorithms for a wide class of cases are proved. Moreover, the geometric properties of the Chebyshev center of a compact set and the differential properties of the Euclidean function of distance to a convex set are essentially used. When implementing the software package, it is possible to run multiple times in order to identify the best found polygon position. A number of examples are simulated.

References

Danilov, D.I., and Lakhtin, A.S., "Optimization of the algorithm for determining the Hausdor distance for convex polygons", Ural Mathematical Journal, 4 (1) (2018) 1423.

Rockafellar, R., "Convex Analysis", Princeton University, Princeton, 1970.

Hausdor, F., "Set theory", Mathematical Society, Providence, RI: Amer, 1957.

Kirchberg, K.J., Jesorsky, O., and Frischholz R.W., "Genetic model optimization for Hausdor distance-based face localization", Biometric Authentication, BioAW 2002. Lecture Notes in Computer Science, 2359 (2002) 103-111.

Huttenlocher, D.P., Klanderman, G.A., and Rucklidge, W.J., "Comparing images using the Hausdor distance", IEEE Transactions on Pattern Analysis and Machine Intelligence, 15 (9) (1993) 850-863.

Gruber, P.M., "Approximation by convex polytopes", Polytopes: Abstract, Convex and Computational, NATO ASI Series (Series C: Mathematical and Physical Sciences), eds: Bisztriczky T., McMullen P., Schneider R., Weiss A.I., 440 (1994) 173-203.

Zhang, J., Liu, Y., "Medical Image Registration Based on Wavelet Transform Using Hausdor Distance", Transactions on Edutainment VII, Part of the Lecture Notes in Computer Science book series (LNCS, volume 7145) (2012) 248-254.

Ushakov, V.N., Lakhtin, A.S., and Lebedev, P.D., "Optimization of the Hausdor distance between sets in Euclidean space", Proceedings of the Steklov Institute of Mathematics, 291 (1) (2015) S222-S238.

Garkavi, A.L., "On the Chebyshev center and convex hull of a set", Uspekhi Mat. Nauk, 19 (6) (1964) 139-145. (in Russian).

Pshenichnyi, B.N., "Vypuklyi analiz i ekstremalnye zadachi", (Convex analysis and extremal problems), Nauka, Moscow, 1980. (in Russian).

Ushakov, V.N., Lebedev, P.D., Tarasyev A.M., and Ushakov A.V., "Optimization of the Hausdor distance between convex polyhedrons in R^3", IFAC-PapersOnLine, 48 (25) (2015) 197-201.

Demyanov, V.F., and Vasilev, L.V., "Nedi erentsiruemaya optimizatsiya", (Nondifferentiable optimization), Nauka, Moscow, 1981. (in Russian).

Natanson, I.P., "Teoriya funktsii veshchestvennoi peremennoi", (Theory of functions of a real variable), Nauka, Moscow, 1974. (in Russian).

Ushakov, V.N., and Lebedev, P.D., "Algorithms for the Construction of an Optimal Cover for Sets in Three-Dimensional Euclidean Space", Proceedings of the Steklov Institute of Mathematics, 293 (1) (2016) S225-S237.

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.

Kazakov, A.L., and Lebedev, P.D., "Algorithms for constructing optimal n-networks in metric spaces", Automation and Remote Control, 78 (7) (2017) 1290-1301.

Lempert, A.A., Kazakov, A.L., and Le, Q.M., "On Reserve and Double Covering Problems for the Sets with Non-Euclidean Metrics", Yugoslav Journal of Operations Research, 29 (1) (2019) 69-79.

Lebedev, P.D., Uspenskii, A.A., and Ushakov, V.N., "Algorithms of Minimization of Hausdor Deviation of a Convex Compact from a Set of Movable Convex Polygons", Chelyabinsk Physical and Mathematical Journal, 5 (2) (2020) 218-231.

Downloads

Published

2020-11-01

Issue

Vol. 30 No. 4 (2020)

Section

Research Articles

License

Copyright (c) 2020 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.