Geodesic
Algorithms of minimization of Hausdorff deviation of a convex compact from a set of movable convex polygons
Čelâbinskij fiziko-matematičeskij žurnal, Tome 5 (2020) no. 2, pp. 218-232.

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

We study the problem of finding the optimal location of a set of moving figures within the boundaries of a given convex set (arena) on the plane. The optimality criterion was chosen to minimize the Hausdorff deviation of the arena from the union of these moving objects. Numerical algorithms are proposed for solving the problem, based on dividing the arena into areas of influence of the figures (into generalized Dirichlet zones) and finding the optimal position of each of them within the boundaries of its area. When creating the algorithms, non-smooth optimization methods and the constructions of the geometric theory of approximations were used. A numerical simulation of the solution of the problem is performed for the case of three moving convex polygons.
Keywords: Hausdorff deviation, convex set, Chebyshev center, minimization, subdifferential. 
@article{CHFMJ_2020_5_2_a2,
     author = {P. D. Lebedev and A. A. Uspenskii and V. N. Ushakov},
     title = {Algorithms of minimization of {Hausdorff} deviation of a convex compact from a set of movable convex polygons},
     journal = {\v{C}el\^abinskij fiziko-matemati\v{c}eskij \v{z}urnal},
     pages = {218--232},
     publisher = {mathdoc},
     volume = {5},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHFMJ_2020_5_2_a2/}
}
TY  - JOUR
AU  - P. D. Lebedev
AU  - A. A. Uspenskii
AU  - V. N. Ushakov
TI  - Algorithms of minimization of Hausdorff deviation of a convex compact from a set of movable convex polygons
JO  - Čelâbinskij fiziko-matematičeskij žurnal
PY  - 2020
SP  - 218
EP  - 232
VL  - 5
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHFMJ_2020_5_2_a2/
LA  - ru
ID  - CHFMJ_2020_5_2_a2
ER  - 
%0 Journal Article
%A P. D. Lebedev
%A A. A. Uspenskii
%A V. N. Ushakov
%T Algorithms of minimization of Hausdorff deviation of a convex compact from a set of movable convex polygons
%J Čelâbinskij fiziko-matematičeskij žurnal
%D 2020
%P 218-232
%V 5
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHFMJ_2020_5_2_a2/
%G ru
%F CHFMJ_2020_5_2_a2
P. D. Lebedev; A. A. Uspenskii; V. N. Ushakov. Algorithms of minimization of Hausdorff deviation of a convex compact from a set of movable convex polygons. Čelâbinskij fiziko-matematičeskij žurnal, Tome 5 (2020) no. 2, pp. 218-232. http://geodesic.mathdoc.fr/item/CHFMJ_2020_5_2_a2/

[1] Bronshtein E.M., “Approximations of convex sets by polytops”, Contemporary Mathematics. Fundamental Directions, 22 (2007), 5–37 (In Russ.)

[2] 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

[3] P. M. Gruber, “Approximation by convex polytopes”, Polytopes: Abstract, Convex and Computational, NATO ASI Series (Series C: Mathematical and Physical Sciences), 440 (1994), 173–203 | MR | Zbl

[4] Hausdorff F., Set theory, Komkniga Publ., Moscow, 2006, 304 pp. (In Russ.)

[5] A. S. Lakhtin, V. N. Ushakov, “Minimization of Hausdorf distance between convex polyhedrons”, Journal of Mathematical Sciences, 126:6 (2005), 1553–1560 | MR | Zbl

[6] Ushakov V.N., Lakhtin A.S., Lebedev P.D., “Optimization of the Hausdorff distance between sets in Euclidean space”, Proceedings of the Steklov Institute of Mathematics, 291:1 (2015), 222–238 | MR

[7] Brusov V.S., Piyavskii S.A., “A computational algorithm for optimally covering a plane region”, USSR Computational Mathematics and Mathematical Physics, 11:2 (1971), 17–27 (In Russ.)

[8] Lebedev P.D., Uspenskii A.A., “Construction of a nonsmooth solution in a time-optimal problem with a low order of smoothness of the target set boundary”, Proceedings of Istitute of Mathematics and Mechanics of Ural Branch of RAS, 25, no. 1, 2019, 108-119 (In Russ.)

[9] Lebedev P.D., Uspenskii A.A., Program for constructing wave fronts and functions of the Euclidean distance to a compact nonconvex set, Certificate of state registration of the computer program no. 2017662074, October 27, 2017

[10] D. Siersma, “Properties of conflict sets in the plan”, Banach Center Publications, 50 (1999), 267–276 | MR | Zbl

[11] Ushakov V.N., Lebedev P.D., “Iterative methods for minimization of the Hausdorff distance between movable polygons”, Bulletin of Udmurt University. Mathematics. Mechanics. Computer Sciences, 27:1 (2017), 86–97 (In Russ.) | MR | Zbl

[12] Polovinkin E.S., Balashov M.V., Elements of convex and strong convex analysis, Fizmatlit Publ., Moscow, 2004, 416 pp. (In Russ.)

[13] Garkavi A.L., “On the Chebyshev center and convex hull of a set”, Advances in Mathematical Sciences, 19:6 (1964), 139–145 (In Russ.) | MR | Zbl

[14] Alimov A.R., Tsar'kov I.G., “Chebyshev centres, Jung constants, and their applications”, Russian Mathematical Surveys, 74:5 (2019), 3–82 | MR | Zbl

[15] Pshenichnyi B.N., Convex analysis and extremal problems, Nauka, Moscow, 1980 (In Russ.) | MR

[16] Dem'yanov V.F., Vasil'ev L.V., Nondifferentiable Optimization, Springer-Verlag, New York, 1985, xvii+452 pp. | MR