ISSN 2226-3594 · EISSN 2410-1737

· Язык: ru

Статья: О МЕТОДЕ УПАКОВКИ ГЕОДЕЗИЧЕСКИХ КРУГОВ В СФЕРИЧЕСКИЙ СЕГМЕНТ С ИСПОЛЬЗОВАНИЕМ ПЛОСКОЙ ПРОЕКЦИИ (2025)

Читать

Читать онлайн

В статье рассматривается задача об оптимальном размещении внутри сферического сегмента заданного числа равных геодезических кругов без пересечений, причем критерием оптимальности является максимизация их радиуса. Данная постановка известна как задача Таммеса и представляет собой один из вариантов классической проблемы о плотнейшей упаковке однотипных объектов в контейнер. Для решения рассмотренной задачи предложен оригинальный двухэтапный численный метод. На первом этапе строится начальное приближение с использованием известных оптимальных упаковок равных кругов в круг большего радиуса, центры которых проектируются специальным образом на сферический сегмент. Доказывается теорема о свойствах проекции, устанавливающая связь между радиусами элементов плоской и сферической упаковок. На втором этапе выполняется процедура улучшения с помощью бильярдного моделирования. Выполнены иллюстрирующие численные расчеты для сферических сегментов различного углового размера. Проведено сравнение их результатов с известными, которое показывает, что предлагаемый метод позволяет находить оптимальные или близкие к ним упаковки за значительно (на два-три порядка) меньшее время, чем при использовании традиционного метода мультистарта. Решена прикладная задача о проектировании сферической фокальной поверхности, которая возникает в инженерной оптике.

Ключевые фразы: упаковка равных кругов, геодезический круг, сферический сегмент, задача таммеса, ДИАГРАММА ВОРОНОГО, численный метод, математическое моделирование

Автор (ы): Казаков Александр Леонидович (Kazakov A. L.), Лемперт Анна Ананьевна (Lempert A. A.), Нгуен Дык Минь (Nguen D. M.)

Журнал: ИЗВЕСТИЯ ИНСТИТУТА МАТЕМАТИКИ И ИНФОРМАТИКИ УДМУРТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

Предпросмотр статьи

Идентификаторы и классификаторы

SCI: Науки о Земле
УДК: 514.174.2. Упаковки

Для цитирования:

КАЗАКОВ А. Л., ЛЕМПЕРТ А. А., НГУЕН Д. М. О МЕТОДЕ УПАКОВКИ ГЕОДЕЗИЧЕСКИХ КРУГОВ В СФЕРИЧЕСКИЙ СЕГМЕНТ С ИСПОЛЬЗОВАНИЕМ ПЛОСКОЙ ПРОЕКЦИИ // ИЗВЕСТИЯ ИНСТИТУТА МАТЕМАТИКИ И ИНФОРМАТИКИ УДМУРТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА. 2025. Т. 65

Текстовый фрагмент статьи

Моя история просмотров (10)

01. Статья: КАЗАНСКИЙ ЭКЗЕМПЛЯР ПЕТЕРБУРГСКОГО ИЗДАНИЯ КОРАНА

02. Статья: ХОЗЯЙСТВЕННО-ПОЛЕЗНЫЕ ПРИЗНАКИ КОРОВ ГОЛШТИНСКОЙ ПОРОДЫ В ЗАВИСИМОСТИ ОТ УРОВНЯ ИНБРИДИНГА

03. Статья: Использование электронных таблиц в решении заданий КЕГЭ по информатике

04. Статья: МНОЖЕСТВА ПРИТЯЖЕНИЯ В АБСТРАКТНОЙ ЗАДАЧЕ О ДОСТИЖИМОСТИ В ТОПОЛОГИЧЕСКОМ ПРОСТРАНСТВЕ

05. Статья: ЗАДАЧА УПРАВЛЕНИЯ ПАРАБОЛИЧЕСКОЙ СИСТЕМОЙ С ПОМЕХАМИ И ВОЗМОЖНЫМИ ИЗМЕНЕНИЯМИ В ДИНАМИКЕ

06. Статья: МЕТОД ПЕРЕМЕННЫХ НАПРАВЛЕНИЙ ДЛЯ НЕЛИНЕЙНОГО ДИФФУЗИОННОГО УРАВНЕНИЯ С ЗАПАЗДЫВАНИЕМ

07. Статья: ИНТЕГРИРОВАНИЕ МОДИФИЦИРОВАННОГО УРАВНЕНИЯ КОРТЕВЕГА-ДЕ ФРИЗА ОТРИЦАТЕЛЬНОГО ПОРЯДКА С ИНТЕГРАЛЬНЫМ ИСТОЧНИКОМ

08. Статья: ИНТЕГРИРОВАНИЕ УРАВНЕНИЯ ТИПА КОРТЕВЕГА-ДЕ ФРИЗА С НАГРУЖЕННЫМ ЧЛЕНОМ В КЛАССЕ ПЕРИОДИЧЕСКИХ ФУНКЦИЙ

09. Статья: ФОРМУЛИРОВКА ФЕНОМЕНОЛОГИЧЕСКИХ ЗАКОНОВ ГРАДИЕНТНОГО ТИПА В ЗАДАЧАХ ВЫЧИСЛИТЕЛЬНОЙ МАКРОМЕХАНИКИ

10. Статья: Многослойная модель компьютера как ориентир при отборе материала для курса информатики

Будьте первым, кто начнет обсуждение

Если у вас возникли вопросы или появились предложения по содержанию статьи, пожалуйста, направляйте их в рамках данной темы.

Создать тему для обсуждения

Список литературы

1. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. М.: Физматлит, 1958.
2. Kepler J. The six-cornered snowflake. Oxford: Oxford University Press, 1966.
3. Castillo I., Kampas F.J., Pintér J.D. Solving circle packing problems by global optimization: numerical results and industrial applications // European Journal of Operational Research. 2008. Vol. 191. Issue 3. P. 786-802. DOI: 10.1016/j.ejor.2007.01.054 EDN: YAMFWB
4. Fodor F. The densest packing of 12 congruent circles in a circle // Contributions to Algebra and Geometry. 2000. Vol. 41. No. 2. P. 401-409. https://zbmath.org/0974.52015.
5. Melissen H. Densest packings of eleven congruent circles in a circle // Geometriae Dedicata. 1994. Vol. 50. No. 1. P. 15-25. DOI: 10.1007/BF01263647 EDN: IMMWJE
6. Zhou J., He K., Zheng J., Li C.-M. Geometric batch optimization for packing equal circles in a circle on large scale // Expert Systems with Applications. 2024. Vol. 50. 123952. DOI: 10.1016/j.eswa.2024.123952 EDN: AFMTDQ
7. Graham R.L., Lubachevsky B.D., Nurmela K.J., Östergard P.R.J. Dense packings of congruent circles in a circle // Discrete Mathematics. 1998. Vol. 181. Issues 1-3. P. 139-154. DOI: 10.1016/S0012-365X(97)00050-2 EDN: INBXDO
8. Ikebe Y., Masuda S., Okuno T. Mixed-integer DC programming based algorithms for the circular packing problem // Journal of the Operations Research Society of Japan. 2023. Vol. 66. Issue 3. P. 153-175. DOI: 10.15807/jorsj.66.153 EDN: WHQYCR
9. Akeb H., Hifi M., M’Hallah R. A beam search algorithm for the circular packing problem // Computers and Operations Research. 2009. Vol. 36. Issue 5. P. 1513-1528. DOI: 10.1016/j.cor.2008.02.003 EDN: VBZEPB
10. The best known packings of equal circles in a circle. http://www.packomania.com.
11. Казаков А.Л., Лебедев П.Д. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости // Вычислительные методы и программирование. 2015. Т. 16. Вып. 2. С. 307-317. DOI: 10.26089/NumMet.v16r230 EDN: YTTXBZ
12. Лебедев П.Д., Лавров Н.Г. Алгоритмы построения оптимальных упаковок шаров в эллипсоиды // Известия Института математики и информатики Удмуртского государственного университета. 2018. Т. 52. C. 59-74. DOI: 10.20537/2226-3594-2018-52-05 EDN: YPDKTB
13. Лебедев П.Д., Кувшинов О.А. Алгоритмы построения субоптимальных покрытий плоских фигур кругами в классах регулярных решеток // Известия Института математики и информатики Удмуртского государственного университета. 2023. Т. 61. С. 76-93. DOI: 10.35634/2226-3594-2023-61-05 EDN: EUAYGS
14. Ушаков В.Н., Лебедев П.Д. Алгоритмы оптимального покрытия множеств на плоскости R2 // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2016. T. 26. Вып. 2. C. 258-270. DOI: 10.20537/vm160212 EDN: WCIEMB
15. Казаков А.Л., Лебедев П.Д. Алгоритмы построения наилучших n-сетей в метрических пространствах // Автоматика и телемеханика. 2017. Вып. 7. C. 141-155. item.asp?id=29393180. EDN: YTFMJF
16. Conway J.H., Sloane N.J.A. Sphere packings, lattices and groups. New York: Springer New York, 1988. DOI: 10.1007/978-1-4757-2016-7
17. Rochal S.B., Konevtsova O.V., Golushko I.Y., Podgornik R. Close packings of identical proteins in small spherical capsids and similar proteinaceous shells // Soft Matter. 2023. Vol. 19. No. 44. P. 8649-8658. DOI: 10.1039/D3SM01106B EDN: XBHUTG
18. Antoniano E. The Tammes problem // Journal de Ciencia e Ingeniería. 2019. Vol. 11. No. 1. P. 72-80. DOI: 10.46571/jci.2019.1.8
19. Lai X., Yue D., Hao J.-K., Glover F., Lü Z. Iterated dynamic neighborhood search for packing equal circles on a sphere // Computers and Operations Research. 2023. Vol. 151. 106121. DOI: 10.1016/j.cor.2022.106121 EDN: IARKQL
20. Barg A., Musin O.R. Codes in spherical caps // Advances in Mathematics of Communications. 2007. Vol. 1. Issue 1. P. 131-149. DOI: 10.3934/amc.2007.1.131
21. Bachoc C., Vallentin F. Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps // European Journal of Combinatorics. 2009. Vol. 30. Issue 3. P. 625-637. DOI: 10.1016/j.ejc.2008.07.017 EDN: MLINOV
22. Melisseny J.B.M. How different can colours be? Maximum separation of points on a spherical octant // Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences. 1998. Vol. 454. No. 1973. P. 1499-1508. DOI: 10.1098/rspa.1998.0218
23. Appelbaum J., Weiss Y. The packing of circles on a hemisphere // Measurement Science and Technology. 1999. Vol. 10. No. 11. P. 1015-1019. DOI: 10.1088/0957-0233/10/11/307 EDN: AYNREB
24. Amore P. Circle packing on spherical caps // Physics of Fluids. 2024. Vol. 36. Issue 9. 097113. DOI: 10.1063/5.0221997 EDN: WJXKFA
25. Tarnai T. Symmetry of golf balls // Katachi ∪ Symmetry. Springer Japan, 1996. P. 207-214. DOI: 10.1007/978-4-431-68407-7_22
26. Cohen S.C., Smith D.E. LAGEOS scientific results: introduction // Journal of Geophysical Research: Solid Earth. 1985. Vol. 90. Issue B11. P. 9217-9220. DOI: 10.1029/JB090iB11p09217
27. Whittemore J.K. A note on geodesic circles // Annals of Mathematics. 1901. Vol. 3. No. 1/4. P. 21-24. DOI: 10.2307/1967629
28. Cossairt O.S., Miau D., Nayar S.K. Gigapixel computational imaging // 2011 IEEE International Conference on Computational Photography (ICCP). IEEE, 2011. P. 1-8. DOI: 10.1109/ICCPHOT.2011.5753115
29. Son H.S., Marks D.L., Hahn J., Kim J., Brady D.J. Design of a spherical focal surface using close-packed relay optics // Optics Express. 2011. Vol. 19. Issue 17. P. 16132-16138. DOI: 10.1364/OE.19.016132
30. Лемперт А.А., Казаков А.Л., Бухаров Д.С. Математическая модель и программная система для решения задачи размещения логистических объектов // Управление большими системами. 2013. Вып. 41. C. 270-284. https://www.mathnet.ru/rus/ubs654. EDN: RDQAWV
31. Бухаров Д.С., Казаков А.Л. Программная система “ВИГОЛТ” для решения задач оптимизации, возникающих в транспортной логистике // Вычислительные методы и программирование. 2012. Т. 13. Вып. 3. C. 65-74. https://www.mathnet.ru/rus/vmp71. EDN: PIXMUB

Выпуск

Т. 65 (2025)

Кол-во страниц: 108 страниц

Другие статьи выпуска

МНОЖЕСТВА ПРИТЯЖЕНИЯ В АБСТРАКТНОЙ ЗАДАЧЕ О ДОСТИЖИМОСТИ В ТОПОЛОГИЧЕСКОМ ПРОСТРАНСТВЕ (2025)

Авторы: Ченцов А. Г.

Рассматриваются абстрактные задачи о достижимости с ограничениями асимптотического характера (ОАХ), в которых результат (аналог множества достижимости) определяется в виде множества притяжения (МП) в топологическом пространстве. Сами ОАХ порождаются при этом непустыми семействами подмножеств исходного множества обычных (доступных для реализации) решений. Среди этих семейств выделяются фильтры: семейство всех возможных МП получается добавлением пустого множества к аналогичному семейству МП, отвечающим каждое ОАХ, порождаемым фильтром; при этом ультрафильтрам всякий раз сопоставляется единственный элемент притяжения. Это позволяет установить ряд важных свойств семейства всех МП, порождаемых фильтрами. Так, в частности, установлено, что данное семейство замкнуто относительно конечных объединений, указаны условия, при которых конечное объединение фильтров порождает МП упомянутого семейства, указано семейство синглетонов, являющихся МП, порождаемыми фильтрами. Само же появление непустых неодноэлементных МП удается истолковать в терминах немаксимальности фильтра, порождающего ОАХ: непустые МП, не являющиеся синглетонами, непременно соответствуют ОАХ, порождаемыми фильтрами, не являющимися ультрафильтрами.

Сохранить в закладках

ПОЛНЫЕ СВОЙСТВА БЛУЖДАЕМОСТИ, КОЛЕБЛЕМОСТИ И ВРАЩАЕМОСТИ ДИФФЕРЕНЦИАЛЬНОЙ СИСТЕМЫ И ИХ СВЯЗЬ С МЕРАМИ ЭТИХ СВОЙСТВ (2025)

Авторы: Сергеев И. Н.

Рассматриваются осцилляционные свойства решений произвольной нелинейной дифференциальной системы (с нулевым решением). Для такой системы определяются нижний, верхний, наинижний и наиверхний показатели колеблемости, блуждаемости и вращаемости. Изучаются связи числовых значений этих показателей как с соответствующими полными и полнейшими осцилляционными свойствами этой системы, так и с противоположными им свойствами: неколеблемостью, неблуждаемостью и невращаемостью. Также изучаются логические связи всех перечисленных свойств друг с другом, причем отсутствие отдельных таких связей подтверждается конкретными контрпримерами. Кроме того, изучается аналогичная связь между наличием у системы какого-либо осцилляционного свойства и единичным или нулевым значением меры соответствующего свойства для самой системы (понятия таких мер вероятностного характера для дифференциальной системы совсем недавно введены в рассмотрение).

Сохранить в закладках

АСИМПТОТИКА КОМПАКТНОЙ СХЕМЫ ДЛЯ РЕШЕНИЯ СУПЕРДИФФУЗИОННОГО УРАВНЕНИЯ С НЕСКОЛЬКИМИ ПЕРЕМЕННЫМИ ЗАПАЗДЫВАНИЯМИ (2025)

Авторы: Лекомцев А. В., Пименов В. Г.

Рассматривается супердиффузионное уравнение с дробными производными Рисса по пространству и с несколькими переменными запаздываниями по времени. Приводятся конструкции дробного аналога компактной схемы с кусочно-кубической интерполяцией и экстраполяцией продолжением, который имеет второй порядок малости относительно шага дискретизации по времени Δ и четвертый относительно шага дискретизации по пространству h. Этот метод является базовым для последующих конструкций. Изучается порядок невязки без интерполяции метода. Выписываются коэффициенты разложения невязки относительно Δ.

Сохранить в закладках

НЕКОТОРЫЕ РЕЗУЛЬТАТЫ О ТОЧКАХ СОВПАДЕНИЯ В b-МЕТРИЧЕСКОМ ПРОСТРАНСТВЕ (2025)

Авторы: Бенараб С., Мерчела В., Хиал Н.

В этой статье мы обобщаем некоторые результаты о точке совпадения для отображений ψ, φ, действующих из метрического пространства в другое пространство - пространство с обобщенным расстоянием.

Сохранить в закладках

О СУЩЕСТВОВАНИИ, ПРОДОЛЖИМОСТИ И ЕДИНСТВЕННОСТИ РЕШЕНИЯ ЗАДАЧИ КОШИ ОДУ ПЕРВОГО ПОРЯДКА, ПОСТАВЛЕННОЙ В ГРАНИЧНОЙ ТОЧКЕ (2025)

Авторы: Басов В. В.

Рассматривается обыкновенное дифференциальное уравнение первого порядка, разрешенное относительно производной. Предполагается, что его правая часть непрерывна на множестве, состоящем из области двумерного евклидова пространства и некоторой части ее границы. Излагается теория, посвященная решению вопросов о существовании, продолжимости и единственности решений ГЗК - задачи Коши, поставленной в граничной точке. Эта теория позволит дополнить существующую теорию ОДУ первого порядка, в которой задача Коши ставится во внутренней точке (ВЗК). Основные результаты в части существования или отсутствия решений ГКЗ были получены в 2020 году, поэтому в данной работе они только систематизируются и дополняются. Новыми являются результаты связанные с продолжимостью, а также с единственностью или неединственностью решений ГЗК. Доказываются теоремы о формальной и локальной единственности решений задачи Коши. При этом постоянно прослеживаются различия между свойствами решений ГЗК и ВЗК. Например, демонстрируется неравносильность понятий формальной и локальной единственности для ГЗК в отличие от ВЗК, что приводит к появлению наряду с точками неединственности и единственности так называемых скрытых точек неединственности.

Сохранить в закладках

Издательство

Издательство: УдГУ
Регион: Россия, Ижевск
Почтовый адрес: 426034, Удмуртская Республика, г. Ижевск, ул. Университетская, 1
Юр. адрес: 426034, Удмуртская Республика, г. Ижевск, ул. Университетская, 1
ФИО: Мерзлякова Галина Витальевна (РЕКТОР)
E-mail адрес: rector@udsu.ru
Контактный телефон: +8 (341) 2681610
Сайт: https://i.udsu.ru/

Все права на тексты и товарные знаки принадлежат их законным владельцам. Подробнее...

Сайт https://sci.ru (далее – сайт) работает по принципу агрегатора – собирает и структурирует информацию из публичных источников в сети Интернет, то есть передает полнотекстовую информацию о товарных знаках в том виде, в котором она содержится в открытом доступе.

Сайт и администрация сайта не используют отображаемые на сайте товарные знаки в коммерческих и рекламных целях, не декларируют своего участия в процессе их государственной регистрации, не заявляют о своих исключительных правах на товарные знаки, а также не гарантируют точность, полноту и достоверность информации.

Все права на товарные знаки принадлежат их законным владельцам!

Сайт носит исключительно информационный характер, и предоставляемые им сведения являются открытыми публичными данными.

Администрация сайта не несет ответственность за какие бы то ни было убытки, возникающие в результате доступа и использования сайта.

Спасибо, понятно.

Сказать «Спасибо»

Вы можете поблагодарить автора за публикацию. Ему (ей) будет приятно.

Наведите камеру на QR-код, чтобы открыть моб. версию страницы.