Methods of optimization of Hausdorff distance between convex rotating figures. (English) Zbl 1474.52019

Lebedev, Pavel; Ushakov, Vladimir

Yugosl. J. Oper. Res. 30, No. 4, 429-442 (2020).

Summary: 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.

MSC:

52B12	Special polytopes (linear programming, centrally symmetric, etc.)
90C25	Convex programming

Keywords:

optimization; Hausdorff distance; rotation; Chebyshev centre; one-sided derivative

Software:

Matlab

References:

[1]	Danilov, D.I., and Lakhtin, A.S., “Optimization of the algorithm for determining the Hausdorff distance for convex polygons”,Ural Mathematical Journal, 4 (1) (2018) 14-23. · Zbl 1456.90157
[2]	Rockafellar, R.,Convex Analysis, Princeton University, Princeton, 1970. · Zbl 0193.18401
[3]	Hausdorff, F.,Set theory, Mathematical Society, Providence, RI: Amer, 1957. · Zbl 0081.04601
[4]	Kirchberg, K.J., Jesorsky, O., and Frischholz R.W. “Genetic model optimization for Hausdorff distance-based face localization. Biometric Authentication”,BioAW 2002. Lecture Notes in Computer Science, 2359, (2002) 103-111. · Zbl 1046.68796
[5]	Huttenlocher, D.P., Klanderman, G.A., and Rucklidge, W.J., “Comparing images using the Hausdorff distance”,IEEE Transactions on Pattern Analysis and Machine Intelligence, 15 (9) (1993) 850-863.
[6]	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. · Zbl 0824.52007
[7]	Zhang, J., Liu, Y., “Medical Image Registration Based on Wavelet Transform Using Hausdorff Distance”,Transactions on Edutainment VII, Part of the Lecture Notes in Computer Science book series (LNCS, volume 7145), (2012) 248-254.
[8]	Ushakov, V.N., Lakhtin, A.S., and Lebedev, P.D., “Optimization of the Hausdorff distance between sets in Euclidean space”,Proceedings of the Steklov Institute of Mathematics, 291 (1) (2015) S222-S238. · Zbl 1338.49070
[9]	Garkavi, A.L., “On the Chebyshev center and convex hull of a set’,Uspekhi Mat. Nauk, 19 (6) (1964) 139-145. (in Russian).
[10]	Pshenichnyi, B.N.,Vypuklyi analiz i ekstremal’nye zadachi, (Convex analysis and extremal problems), Nauka, Moscow, 1980. (in Russian).
[11]	Ushakov, V.N., Lebedev, P.D., Tarasyev A.M., and Ushakov A.V. “Optimization of the Hausdorff distance between convex polyhedrons inR3”,IFAC-PapersOnLine, 48 (25) (2015) 197-201.
[12]	Dem’yanov, V.F., and Vasil’ev, L.V.,Nedifferentsiruemaya optimizatsiya, (Nondifferentiable optimization), Nauka, Moscow, 1981. (in Russian).
[13]	Natanson, I.P.,Teoriya funktsii veshchestvennoi peremennoi, (Theory of functions of a real variable), Nauka, Moscow, 1974. (in Russian).
[14]	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. · Zbl 1385.90024
[15]	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.
[16]	Kazakov, A.L., and Lebedev, P.D., “Algorithms for constructing optimaln-networks in metric spaces”,Automation and Remote Control, 78 (7) (2017) 1290-1301. · Zbl 1373.93092
[17]	Lempert, A.A., Kazakov, A.L., and Le, Q.M., “On Reserve and Double Covering Problems fo the Sets with Non-Euclidean Metrics”,Yugoslav Journal of Operations Research, 29 (1) (2019) 69-79.
[18]	Lebedev, P.D., Uspenskii, A.A., and Ushakov, V.N., “Algorithms of Minimization of Husdorff Deviation of a Convex Compact from a Set of Movable Convex Polygons”,Chelyabinsk Physical and Mathematical Journal, 5 (2) (2020) 218