Итерационные алгоритмы минимизации хаусдорфова расстояния между выпуклыми многогранниками
Ключевые слова:
хаусдорфово расстояние, минимизация, субдифференцал, чебышёвский центр
Аннотация
Рассматривается проблема поиска оптимального расположения подвижных тел в трехмерном евклидовом пространстве. Исследуется задача об отыскании такого положения двух заданных многогранников $A$ и $B$, при котором хаусдорфово расстояние между ними было бы минимальным. Для ее решения используется аппарат выпуклого и негладкого анализа, а также методы вычислительной геометрии. Разработаны итерационные алгоритмы и выполнено обоснование корректности их работы. Создан программный комплекс, его работа проиллюстрирована на конкретных примерах.
Литература
1. Бронштейн Е.М. Аппроксимация выпуклых множеств многогранниками // Современная математика. Фундаментальные направления. 2007. Т. 22. С. 5-37.
http://mi.mathnet.ru/cmfd83
2. Alt H., Braß P., Godau M., Knauer C., Wenk C. Computing the Hausdorff distance of geometric patterns and shapes // Discrete and Computational Geometry. Berlin-Heidelberg: Springer, 2003. P. 65-76.
https://doi.org/10.1007/978-3-642-55566-4_4
3. Gruber P.M. Approximation by convex polytopes // Polytopes: abstract, convex and computational. Dordrecht: Springer, 1994. P. 173-203.
https://doi.org/10.1007/978-94-011-0924-6_8
4. Huttenlocher D.P., Klanderman G.A., Rucklidge W.J. Comparing images using the Hausdorff distance // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1993. Vol. 15. Issue 9. P. 850-863.
https://doi.org/10.1109/34.232073
5. Theodoridis S., Koutroumbas K. Pattern recognition. Academic Press, 2006.
https://doi.org/10.1016/B978-0-12-369531-4.X5000-8
6. Ушаков В.Н., Лахтин А.С., Лебедев П.Д. Оптимизация хаусдорфова расстояния между множествами в евклидовом пространстве // Труды Института математики и механики УрО РАН. 2014. Т. 20. № 3. C. 291-308.
http://mi.mathnet.ru/timm1101
7. Ушаков В.Н., Лебедев П.Д. Итерационные методы минимизации хаусдорфова расстояния между подвижными многоугольниками // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2017. Т. 27. Вып. 1. С. 86-97.
https://doi.org/10.20537/vm170108
8. Ushakov V.N., Lebedev P.D., Tarasyev A.M., Ushakov A.V. Optimization of the Hausdorff distance between convex polyhedrons in $\mathbf{R}^3$ // IFAC-PapersOnLine. 2015. Vol. 48. Issue 25. P. 197-201.
https://doi.org/10.1016/j.ifacol.2015.11.084
9. Гаркави А.Л. О чебышёвском центре и выпуклой оболочке множества // УМН. 1964. Т. 19. Вып. 6 (120). С. 139-145.
http://mi.mathnet.ru/umn6276
10. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980.
11. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973.
12. Danilov D.I., Lakhtin A.S. Optimization of the algorithm for determining the Hausdorff distance for convex polygons // Ural Mathematical Journal. 2018. Vol. 4. No. 1. P. 14-23.
https://doi.org/10.15826/umj.2018.1.002
13. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979.
14. Белобров П.К. К вопросу о чебышёвском центре множества // Известия высших учебных заведений. Математика. 1964. № 1. C. 3-9.
http://mi.mathnet.ru/ivm2345
15. Лебедев П.Д., Успенский А.А., Ушаков В.Н. Алгоритмы минимизации хаусдорфова отклонения выпуклого компакта от набора подвижных выпуклых многоугольников // Челябинский физико-математический журнал. 2020. Т. 5. Вып 2. С. 218-232.
https://doi.org/10.24411/2500-0101-2020-15209
16. Лебедев П.Д., Лавров Н.Г. Алгоритмы построения оптимальных упаковок шаров в эллипсоиды // Известия Института математики и информатики Удмуртского государственного университета. 2018. Т. 52. С. 59-74.
https://doi.org/10.20537/2226-3594-2018-52-05
http://mi.mathnet.ru/cmfd83
2. Alt H., Braß P., Godau M., Knauer C., Wenk C. Computing the Hausdorff distance of geometric patterns and shapes // Discrete and Computational Geometry. Berlin-Heidelberg: Springer, 2003. P. 65-76.
https://doi.org/10.1007/978-3-642-55566-4_4
3. Gruber P.M. Approximation by convex polytopes // Polytopes: abstract, convex and computational. Dordrecht: Springer, 1994. P. 173-203.
https://doi.org/10.1007/978-94-011-0924-6_8
4. Huttenlocher D.P., Klanderman G.A., Rucklidge W.J. Comparing images using the Hausdorff distance // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1993. Vol. 15. Issue 9. P. 850-863.
https://doi.org/10.1109/34.232073
5. Theodoridis S., Koutroumbas K. Pattern recognition. Academic Press, 2006.
https://doi.org/10.1016/B978-0-12-369531-4.X5000-8
6. Ушаков В.Н., Лахтин А.С., Лебедев П.Д. Оптимизация хаусдорфова расстояния между множествами в евклидовом пространстве // Труды Института математики и механики УрО РАН. 2014. Т. 20. № 3. C. 291-308.
http://mi.mathnet.ru/timm1101
7. Ушаков В.Н., Лебедев П.Д. Итерационные методы минимизации хаусдорфова расстояния между подвижными многоугольниками // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2017. Т. 27. Вып. 1. С. 86-97.
https://doi.org/10.20537/vm170108
8. Ushakov V.N., Lebedev P.D., Tarasyev A.M., Ushakov A.V. Optimization of the Hausdorff distance between convex polyhedrons in $\mathbf{R}^3$ // IFAC-PapersOnLine. 2015. Vol. 48. Issue 25. P. 197-201.
https://doi.org/10.1016/j.ifacol.2015.11.084
9. Гаркави А.Л. О чебышёвском центре и выпуклой оболочке множества // УМН. 1964. Т. 19. Вып. 6 (120). С. 139-145.
http://mi.mathnet.ru/umn6276
10. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980.
11. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973.
12. Danilov D.I., Lakhtin A.S. Optimization of the algorithm for determining the Hausdorff distance for convex polygons // Ural Mathematical Journal. 2018. Vol. 4. No. 1. P. 14-23.
https://doi.org/10.15826/umj.2018.1.002
13. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979.
14. Белобров П.К. К вопросу о чебышёвском центре множества // Известия высших учебных заведений. Математика. 1964. № 1. C. 3-9.
http://mi.mathnet.ru/ivm2345
15. Лебедев П.Д., Успенский А.А., Ушаков В.Н. Алгоритмы минимизации хаусдорфова отклонения выпуклого компакта от набора подвижных выпуклых многоугольников // Челябинский физико-математический журнал. 2020. Т. 5. Вып 2. С. 218-232.
https://doi.org/10.24411/2500-0101-2020-15209
16. Лебедев П.Д., Лавров Н.Г. Алгоритмы построения оптимальных упаковок шаров в эллипсоиды // Известия Института математики и информатики Удмуртского государственного университета. 2018. Т. 52. С. 59-74.
https://doi.org/10.20537/2226-3594-2018-52-05
Поступила в редакцию
2021-03-01
Опубликована 2021-05-20
Опубликована 2021-05-20