Научный журнал Байкальского государственного университета
System Analysis &
Mathematical Modeling
Издается с 2019 года
Menu
РусскийEnglish

Информация о статье

Название статьи:

Покрытие эллипсоида равными шарами

Авторы:
Нгуен Д.М., аспирант, институт информационных технологий и анализа данных, Иркутский национальный исследовательский технический университет, г. Иркутск, Российская Федерация, nguyenducminh.mt@gmail.com
В рубрике:
МАТЕМАТИЧЕСКИЕ НАУКИ
Год: 2025 Том: 7 Номер журнала: 2
Страницы: 274-289
Тип статьи: Научная статья
УДК: 514.174.3, 004.942
DOI: 10.17150/2713-1734.2025.7(2).274-289
Аннотация:
В статье рассматривается задача о построении тончайшего покрытия эллипсоида равными шарами, причем их центры должны лежать на эллипсоиде. Критерием оптимизации является минимизация радиуса покрывающих шаров. Подобные задачи возникают в приложениях, в частности, в медицине. Для решения задачи предложен эвристический алгоритм, основанный на интегрированном применении геодезической диаграммы Вороного на эллипсоиде и оптико-геометрической аналогии. Для оценки качества покрытия реализован численный метод расчета площади пересечения эллипсоида и шара. Проведены вычислительные эксперименты для различных эллипсоидов, найденные покрытия сравнивались с аналогичными покрытиями сфер, имеющих ту же площадь. Выполнено моделирование облучения поверхности опухоли сферическими радиационными лучами.
Ключевые слова: тончайшее покрытие, покрытие эллипсоида, диаграмма Вороного, оптико-геометрическая аналогия, оптимизация, математическое моделирование
Скачать полный текст статьи
Список цитируемой литературы:
  • Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве / Л.Ф. Тот. - Москва : Физматлит, 1958. - 364 c.
  • Тахонов И.И. О некоторых задачах покрытия плоскости кругами / И.И. Тахонов. - EDN RXPVKN // Дискретный анализ и исследование операций. - 2014. - Т. 21, № 1. - С. 84-102.
  • Лебедев П.Д. Алгоритмы построения оптимального покрытия плоских фигур наборами кругов линейно различающихся радиусов / П.Д. Лебедев, К.Л. Стойчин // Известия Иркутского государственного университета. Серия Математика - 2023. - Т. 46. - С. 35-50.
  • Toth G.F. Miscellaneous Problems about Packing and Covering / G.F. Toth, L.F. Toth, W. Kuperberg // Grundlehren der Mathematischen Wissenschaften. - Cham : Springer. - 2023. - Vol. 360. - P. 313-336.
  • Fu M. Lower Bounds on Lattice Covering Densities of Simplices / M. Fu, F. Xue, C. Zong. - DOI 10.1137/22M1514155 // SIAM Journal on Discrete Mathematics. - 2023 - Vol. 37, no. 3. - P. 1788-1804.
  • Bezdek K. From the Separable Tammes Problem to Extremal Distributions of Great Circles in the Unit Sphere / K. Bezdek, Z. Langi // Discrete Comput Geom. - 2023. - Vol. 72. - P. 269-309.
  • Liberti L. Optimal Configuration of Gamma Ray Machine Radiosurgery Units: the Sphere Covering Subproblem / L. Liberti, N. Maculan, Y. Zhang. - DOI 10.1007/s11590-008-0095-4 // Optimization Letter. - 2009. - Vol. 3 - P. 109-121.
  • The Discrete Ellipsoid Covering Problem: A Discrete Geometric Programming Approach / R.Q. do Nascimento, A.F.U. dos Santos Macambira, L.D.A.F. Cabral, R.V. Pinto. - DOI 10.1016/j.dam.2012.10.016 // Discrete Applied Mathematics. - 2014. - Vol. 164 - P. 276-285.
  • Лемперт А.А. Математическая модель и программная система для решения задачи размещения логистических объектов / А.А. Лемперт, А.Л. Казаков, Д.С. Бухаров. - EDN RDQAWV // Управление большими системами. - 2013. - № 41. - С. 270-284.
  • Казаков А.Л. Об одном численном методе решения некоторых задач оптимизации, возникающих в транспортной логистике / А.Л. Казаков, А.А. Лемперт, Д.С. Бухаров. - EDN NXNAWN // Вестник Иркутского государственного технического университета. - 2011. - № 6. - С. 6-12.
  • Fodor F. Covering the Sphere by Equal Zones / F. Fodor, V. Vigh, T. Zarnocz. - DOI 10.1007/s10474-016-0613-2 // Acta Math. Hungar. - 2016. - Vol. 149, no. 2. - P. 478-489.
  • Галиев Ш.И. Многократные упаковки и покрытия сферы / Ш.И. Галиев // Дискретная математика. - 1996. - Т. 8, № 3. - С. 148-160.
  • Казаков А.Л. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике / А.Л. Казаков, А.А. Лемперт. - EDN NXCWVD // Автоматика и телемеханика. - 2011. - Т. 72, № 7. - С. 50-57.
  • Казаков А.Л. Алгоритмы построения наилучших N-сетей в метрических пространствах / А.Л. Казаков, П.Д. Лебедев. - EDN YTFMJF // Автоматика и телемеханика. - 2017. - № 7. - С. 141-155.
  • Лемперт А.А. О задаче покрытия сферических фигур равными сферическими сегментами / А.А. Лемперт, П.Д. Лебедев, Д.М. Нгуен. - DOI 10.21538/0134-4889-2024-30-1-142-155. - EDN LTIMOY // Труды Института математики и механики УрО РАН. - 2024. - Т. 30, № 1. - С. 142-155.
  • Dumer I. Covering an Ellipsoid with Equal Balls / I. Dumer. - DOI 10.1016/j.jcta.2006.03.021 // Journal of Combinatorial Theory. - 2006. - Vol. 113. - P. 1667-1676.
  • Dumer I. On Coverings of Ellipsoids in Euclidean Spaces / I. Dumer, M.S. Pinsker, V.V. Prelov. - DOI 10.1109/TIT.2004.834759 // Journal of Combinatorial Theory, Series A. - 2004. - Vol. 50, no. 10. - P. 2348-2356.
  • Fortune S. A Sweepline Algorithm for Voronoi Diagrams / S. Fortune // Algorithmica. - 1987. - Vol. 2. - P. 153-174.
  • Panou G. Solving the Geodesics on the Ellipsoid as a Boundary Value Problem / G. Panou, D. Delikaraoglou, R. Korakitis. - DOI 10.2478/jogs-2013-0007 // Journal of Geodetic Science. - 2013. - Vol. 3, no. 1. - P. 40-47.
  • Panou G. The Geodesic Boundary Value Problem and its Solution on a Triaxial Ellipsoid / G. Panou. - DOI 10.2478/jogs-2013-0028 // Journal of Geodetic Science. - 2013. - Vol. 3, no. 3. - P. 240-249.
  • Tarnai T. Covering a Sphere by Equal Circles, and the Rigidity of its Graph / T. Tarnai, Zs. Gaspar. - DOI 10.1017/S0305004100070134 // Mathematical Proceedings of the Cambridge Philosophical Society. - 1991. - Vol. 110, no. 1. - P. 71-89.
  • Ким А.В. Рецидив нейроэпителиальных опухолей головного мозга у детей : дис. … д-ра мед. наук : 14.01.18 / А.В. Ким. - Санкт-Петербург, 2020. - 373 с.