Optimization of the algorithm for determining the Hausdorff distance for convex polygons. (English) Zbl 1456.90157

Summary: The paper provides a brief historical analysis of problems that use the Hausdorff distance; provides an analysis of the existing Hausdorff distance optimization elements for convex polygons; and demonstrates an optimization approach. The existing algorithm served as the basis to propose low-level optimization with super-operative memory, ensuring the finding a precise solution by a full search of the corresponding pairs of vertices and sides of polygons with exclusion of certain pairs of vertices and sides of polygons. This approach allows a significant acceleration of the process of solving the set problem.


90C30 Nonlinear programming
90C90 Applications of mathematical programming
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI MNR


[1] Arutyunov A.V., Lectures on Convex and Polysemantic Analysis, Fizmatlit, Moscow, 2014, 184 pp.
[2] Bronshtein E.M., “Approximation of convex sets by polytopes”, Contemporary Mathematics. Fundamental Directions, 22 (2007), 5-37 (in Russian)
[3] Chernousko F.L., Estimation of the Phase State of Dynamic Systems, Nauka, Moscow, 1988 (in Russian)
[4] Gruber P.M., “Approximation by convex polytopes”, Polytopes: Abstract, Convex and Computational, NATO ASI Series (Series C: Mathematical and Physical Sciences), 440, eds. Bisztriczky T., McMullen P., Schneider R., Weiss A.I., 1994, 173-203
[5] Gruber P.M., “Comparision of best and random approximation of convex bodies by polytopes”, Rend. Circ. Mat. Palermo, 50 (1997), 189-216 · Zbl 0896.52014
[6] Huttenlocher D.P., Klanderman G.A., Rucklidge W.J., “Comparing images using the Hausdorff distance”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 15:9 (1993), 850-863
[7] Huttenlocher D.P., Rucklidge W.J., A multi-resolution technique for comparing images using the Hausdorff distance, Technical Report № 1321,
[8] Jesorsky O., Kirchberg K.J., Frischholz R.W., “Robust face detection using the Hausdorff distance”, Audio- and Video-Based Biometric Person Authentication, AVBPA 2001, Lecture Notes in Computer Science, 2091, 2001, 90-95 · Zbl 0987.68966
[9] Kirchberg K.J., Jesorsky O., 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
[10] Kurzhansky A.B., Filippova T.F., “On the description of sets of surviving trajectories of differential inclusion”, Report of AS of the USSR, 289:1 (1986), 38-41
[11] Lakhtin A.S., Constructions of Non-smooth and Polysemantic Analyses in Problems of Dynamic Optimization and the Theory of Hamilton-Jacobi Equations, Dr. phys. and math. sci. diss., Yekaterinburg, 2001 (in Russian)
[12] Lakhtin A.S., Ushakov V.N., “The problem of optimizing the Hausdorff distance between two convex polyhedra”, Modern Mathematics and its Applications, 9 (2003), 6-67 (in Russian)
[13] Lebedev P.D., Uspensky A.A., “Procedures for calculating the non-convexity of a planar set”, Comput. Math. Math. Phys., 49:3 (2009), 418-427 · Zbl 1224.52022
[14] Petrov N.N., Introduction to Convex Analysis: Study Guide, 2009 (in Russian)
[15] Romanov A.V., Kataeva L.Yu., “On the use of superconvertive memory for the solution of a system of algebraic equations by the method of alternating directions”, The Future of the Engineering Science, VII International Scientific and Technical Youth Conference, book of Abstracts, 2008, 33-34 (in Russian)
[16] Rosenblum M., Yacoob Y., Davis L., “Human expression recognition from motion using a radial basis function network architecture”, IEEE Transactions on Neural Networks, 7:5 (1996), 1121-1138
[17] Schlesinger M.I., Vodolazskii Y.V., Yakovenko V.M., “Recognizing the similarity of polygons in a strengthened Hausdorff metric”, Cybern. Syst. Anal., 50:3 (2014), 476-486 · Zbl 1311.65023
[18] Ushakov V.N., Lebedev P.D., “Iterative methods for minimization of the Hausdorff distance between movable polygons”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 27:1 (2014), 86-97 (in Russian) · Zbl 1376.49039
[19] Ushakov V.N., Lakhtin A.S., Lebedev P.D., “Optimization of the Hausdorff distance between sets in Euclidean space”, Proc. Steklov Inst. Math., 291:1 (2015), 222-238 · Zbl 1338.49070
[20] Yaksubaev K.D., Shuklina Yu.A., “Metric space of unlimited convex sets and unlimited polyhedron”, International Research Journal, 5:59, part 3 (2017), 162-164
[21] Zhang J., Liu Y., “Medical image registration based on wavelet transform using Hausdorff distance”, Transactions on Edutainment VII, Lecture Notes in Computer Science, 7145, 2012, 248-254
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.