Geodesic
Optimization of the algorithm for determining the Hausdorff distance for convex polygons
Ural mathematical journal, Tome 4 (2018) no. 1, pp. 14-23 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: Optimization, Optimal control theory, Differential games, Theory of image recognition.
Mots-clés : Hausdorff distance, Polygon 
@article{UMJ_2018_4_1_a1,
     author = {Dmitry I. Danilov and Alexey S. Lakhtin},
     title = {Optimization of the algorithm for determining the {Hausdorff} distance for convex polygons},
     journal = {Ural mathematical journal},
     pages = {14--23},
     year = {2018},
     volume = {4},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UMJ_2018_4_1_a1/}
}
TY  - JOUR
AU  - Dmitry I. Danilov
AU  - Alexey S. Lakhtin
TI  - Optimization of the algorithm for determining the Hausdorff distance for convex polygons
JO  - Ural mathematical journal
PY  - 2018
SP  - 14
EP  - 23
VL  - 4
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/UMJ_2018_4_1_a1/
LA  - en
ID  - UMJ_2018_4_1_a1
ER  - 
%0 Journal Article
%A Dmitry I. Danilov
%A Alexey S. Lakhtin
%T Optimization of the algorithm for determining the Hausdorff distance for convex polygons
%J Ural mathematical journal
%D 2018
%P 14-23
%V 4
%N 1
%U http://geodesic.mathdoc.fr/item/UMJ_2018_4_1_a1/
%G en
%F UMJ_2018_4_1_a1
Dmitry I. Danilov; Alexey S. Lakhtin. Optimization of the algorithm for determining the Hausdorff distance for convex polygons. Ural mathematical journal, Tome 4 (2018) no. 1, pp. 14-23. http://geodesic.mathdoc.fr/item/UMJ_2018_4_1_a1/

[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) | MR

[3] Chernousko F.L., Estimation of the Phase State of Dynamic Systems, Nauka, Moscow, 1988 (in Russian) | MR

[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 | DOI | MR

[5] Gruber P.M., “Comparision of best and random approximation of convex bodies by polytopes”, Rend. Circ. Mat. Palermo, 50 (1997), 189–216 | MR | Zbl

[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 | DOI

[7] Huttenlocher D.P., Rucklidge W.J., A multi-resolution technique for comparing images using the Hausdorff distance, Technical Report No 1321, , Cornell University, 1992 http://hdl.handle.net/1813/6165

[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 | DOI | Zbl

[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 | DOI | Zbl

[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 | MR

[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) | MR

[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 | DOI | Zbl

[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 | DOI

[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 | DOI | Zbl

[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) | DOI

[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 | DOI

[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 | DOI

[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 | DOI