Open AccessMethods of optimization of Hausdorff distance between convex rotating figures
Author(s) -
П. Д. Лебедев,
В. Н. Ушаков
Publication year - 2020
Publication title -
yugoslav journal of operations research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.221
H-Index - 21
eISSN - 1820-743X
pISSN - 0354-0243
DOI - 10.2298/yjor191125027l
Subject(s) - mathematics , hausdorff distance , polygon (computer graphics) , star shaped polygon , polygon covering , convex polygon , convex set , rectilinear polygon , rotation (mathematics) , regular polygon , algorithm , combinatorics , convex optimization , computer science , simple polygon , geometry , mathematical analysis , telecommunications , frame (networking)
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.