<!DOCTYPE article
PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.4 20190208//EN"
       "JATS-journalpublishing1.dtd">
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" article-type="research-article" dtd-version="1.4" xml:lang="en">
 <front>
  <journal-meta>
   <journal-id journal-id-type="publisher-id">Modern Technologies and Scientific and Technological Progress</journal-id>
   <journal-title-group>
    <journal-title xml:lang="en">Modern Technologies and Scientific and Technological Progress</journal-title>
    <trans-title-group xml:lang="ru">
     <trans-title>современные технологии и научно-технический прогресс</trans-title>
    </trans-title-group>
   </journal-title-group>
   <issn publication-format="print">2686-9896</issn>
  </journal-meta>
  <article-meta>
   <article-id pub-id-type="publisher-id">82084</article-id>
   <article-id pub-id-type="doi">10.36629/2686-9896-2024-1-156-158</article-id>
   <article-categories>
    <subj-group subj-group-type="toc-heading" xml:lang="ru">
     <subject>ТЕХНИЧЕСКАЯ КИБЕРНЕТИКА</subject>
    </subj-group>
    <subj-group subj-group-type="toc-heading" xml:lang="en">
     <subject>TECHNICAL CYBERNETICS</subject>
    </subj-group>
    <subj-group>
     <subject>ТЕХНИЧЕСКАЯ КИБЕРНЕТИКА</subject>
    </subj-group>
   </article-categories>
   <title-group>
    <article-title xml:lang="en">NUMERICAL ALGORITHM FOR COVERING SURFACES OF REVOLUTION BY BALLS WITH EQUAL RADII</article-title>
    <trans-title-group xml:lang="ru">
     <trans-title>ЧИСЛЕННЫЙ АЛГОРИТМ ПОСТРОЕНИЯ ПОКРЫТИЯ ПОВЕРХНОСТЕЙ ВРАЩЕНИЯ ШАРАМИ С РАВНЫМИ РАДИУСАМИ</trans-title>
    </trans-title-group>
   </title-group>
   <contrib-group content-type="authors">
    <contrib contrib-type="author">
     <name-alternatives>
      <name xml:lang="ru">
       <surname>Нгуен</surname>
       <given-names>Дык Минь </given-names>
      </name>
      <name xml:lang="en">
       <surname>Nguyen</surname>
       <given-names>Dyk Min </given-names>
      </name>
     </name-alternatives>
    </contrib>
   </contrib-group>
   <pub-date publication-format="print" date-type="pub" iso-8601-date="2024-04-22T05:26:55+03:00">
    <day>22</day>
    <month>04</month>
    <year>2024</year>
   </pub-date>
   <pub-date publication-format="electronic" date-type="pub" iso-8601-date="2024-04-22T05:26:55+03:00">
    <day>22</day>
    <month>04</month>
    <year>2024</year>
   </pub-date>
   <volume>2024</volume>
   <issue>1</issue>
   <fpage>156</fpage>
   <lpage>158</lpage>
   <history>
    <date date-type="received" iso-8601-date="2024-04-18T00:00:00+03:00">
     <day>18</day>
     <month>04</month>
     <year>2024</year>
    </date>
   </history>
   <self-uri xlink:href="https://angtu.editorum.ru/en/nauka/article/82084/view">https://angtu.editorum.ru/en/nauka/article/82084/view</self-uri>
   <abstract xml:lang="ru">
    <p>Рассмотрена задача построения тончайшего покрытия поверхностей вращения шарами, радиусы которых равны и заранее неизвестны. Предложен эвристический алгоритм ее решения, основанный на совместном применении оптико-геометрического подхода и геодезической диаграммы Вороного. Выполнены расчеты для некоторых поверхностей вращения, включая сферу</p>
   </abstract>
   <trans-abstract xml:lang="en">
    <p>The paper focuses on the problem of constructing the thinnest covering for surfaces of revolution by equal balls whose radii are unknown in advance. A heuristic algorithm based on the joint applying the optical-geometric approach and the geodesic Voronoi diagram is proposed. Calculations for some surfaces of revolution, including a sphere, are carried out</p>
   </trans-abstract>
   <kwd-group xml:lang="ru">
    <kwd>задача покрытия</kwd>
    <kwd>поверхность вращения</kwd>
    <kwd>равные шары</kwd>
    <kwd>диаграмма Вороного</kwd>
   </kwd-group>
   <kwd-group xml:lang="en">
    <kwd>covering problem</kwd>
    <kwd>surface of revolution</kwd>
    <kwd>equal balls</kwd>
    <kwd>Voronoi diagram</kwd>
   </kwd-group>
  </article-meta>
 </front>
 <body>
  <p>Построение минимальных (тончайших) покрытий и максимальных (плотнейших) упаковок относится к классическим формулировкам вычислительной геометрии [1]. Такие проблемы изучаются уже на протяжении десятилетий, но до сих пор остаются актуальными [2,3]. Преимущественно рассматриваются покрытия плоских фигур конгруэнтными кругами в различных постановках [4-7]. Задача оптимального покрытия криволинейной поверхности заданным числом равных шаров изучена гораздо меньше. Наиболее очевидным приложением является размещение однотипных беспроводных датчиков и проектирование глобальных навигационных и коммуникационных систем. Во всех случаях покрываемая поверхность является поверхностью вращения. Другим применением является перенос изображения с криволинейной поверхности на плоскость для лазерной размерной обработки поверхностей вращения через плоскую маску [8].Отметим, что во всех этих прикладных задачах может возникать искажение сигнала, приводящее к нарушению сферической формы зоны действия датчика или передатчика. Как правило, это свойство не учитывается. В данной работе предлагается использовать специальную неевклидову метрику для учета таких эффектов. Она отражает свойства окружающей среды, заменяя физическое расстояние временем, необходимым для его прохождения [9].Математически, рассматриваемая задача покрытия поверхности S  имеет видR→min, ρOi,p≤R, ∀p∈S, Oi∈S, i=1,…,n. Здесь n   – число покрывающих шаров с центрами Oi  радиусом R . Функция ρ(a,b)  задает расстояние между двумя точками и определяется из решения задачи:ρa,b=dGf(x,y,z)G∈G(a,b)min. Если непрерывная функция f(x,y,z)  есть мгновенная скорость движения, то ρ(a,b)  – минимальное время перемещения между точками a,b∈S .Для решения данной задачи предложен эвристический алгоритм, основанный на совместном применении оптико-геометрического подхода [9] и геодезической диаграммы Вороного, позволяющий находить локально-оптимальные решения как для евклидова так и для неевклидова расстояния. Предложена глобализирующая процедура на основе метода мультистарта. Проведен вычислительный эксперимент, в ходе которого решались серии задач покрытия сферы, цилиндра и тора. В случаях, когда поверхности допускают развертывание, дополнительно проводилось покрытие разверток. На рисунке 1 представлены покрытия единичной сферы 20 кругами (слева) и 100 кругами (справа) и соответствующие им сферические диаграммы Вороного.    Рис. 1. Покрытие единичной сферы равными шарами. Проведено сравнение результатов расчетов с известными, показавшее, что традиционные геометрические методы являются более быстрыми, а предложенный  алгоритм дает более точные результаты.</p>
 </body>
 <back>
  <ref-list>
   <ref id="B1">
    <label>1.</label>
    <citation-alternatives>
     <mixed-citation xml:lang="ru">Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. М.: Физматлит, 1958. 364 c.</mixed-citation>
     <mixed-citation xml:lang="en">Tot L.F. Raspolozheniya na ploskosti, na sfere i v prostranstve. M.: Fizmatlit, 1958. 364 c.</mixed-citation>
    </citation-alternatives>
   </ref>
   <ref id="B2">
    <label>2.</label>
    <citation-alternatives>
     <mixed-citation xml:lang="ru">Bezdek K., Langi Z. From the separable Tammes problem to extremal distri-butions of great circles in the unit sphere // Discrete Comput. Geom. 2023. https://doi.org/10.1007/s00454-023-00509-w.</mixed-citation>
     <mixed-citation xml:lang="en">Bezdek K., Langi Z. From the separable Tammes problem to extremal distri-butions of great circles in the unit sphere // Discrete Comput. Geom. 2023. https://doi.org/10.1007/s00454-023-00509-w.</mixed-citation>
    </citation-alternatives>
   </ref>
   <ref id="B3">
    <label>3.</label>
    <citation-alternatives>
     <mixed-citation xml:lang="ru">Toth. G.F., Toth. L.F., Kuperberg W. Miscellaneous problems about packing and covering // Lagerungen. Grundlehren der mathematischen Wissenschaften. 2023. Vol. 360. P. 313-336.</mixed-citation>
     <mixed-citation xml:lang="en">Toth. G.F., Toth. L.F., Kuperberg W. Miscellaneous problems about packing and covering // Lagerungen. Grundlehren der mathematischen Wissenschaften. 2023. Vol. 360. P. 313-336.</mixed-citation>
    </citation-alternatives>
   </ref>
   <ref id="B4">
    <label>4.</label>
    <citation-alternatives>
     <mixed-citation xml:lang="ru">Тахонов И.И. О некоторых задачах покрытия плоскости кругами // Дискретный анализ и исследование операций. 2014. Vol. 21, № 1. P. 84-102.</mixed-citation>
     <mixed-citation xml:lang="en">Tahonov I.I. O nekotoryh zadachah pokrytiya ploskosti krugami // Diskretnyy analiz i issledovanie operaciy. 2014. Vol. 21, № 1. P. 84-102.</mixed-citation>
    </citation-alternatives>
   </ref>
   <ref id="B5">
    <label>5.</label>
    <citation-alternatives>
     <mixed-citation xml:lang="ru">Dorninger D. Thinnest covering of the Euclidean plane with incongruent cir-cles // Analysis and Geometry in Metric Spaces. 2017. Vol. 5. P. 40–46.</mixed-citation>
     <mixed-citation xml:lang="en">Dorninger D. Thinnest covering of the Euclidean plane with incongruent cir-cles // Analysis and Geometry in Metric Spaces. 2017. Vol. 5. P. 40–46.</mixed-citation>
    </citation-alternatives>
   </ref>
   <ref id="B6">
    <label>6.</label>
    <citation-alternatives>
     <mixed-citation xml:lang="ru">Лебедев П.Д., Стойчин К.Л. Алгоритмы построения оптимального покрытия плоских фигур наборами кругов линейно различающихся радиусов // Известия Иркутского государственного университета. Серия Математика. 2023. Т. 46. C. 35-50.</mixed-citation>
     <mixed-citation xml:lang="en">Lebedev P.D., Stoychin K.L. Algoritmy postroeniya optimal'nogo pokrytiya ploskih figur naborami krugov lineyno razlichayuschihsya radiusov // Izvestiya Irkutskogo gosudarstvennogo universiteta. Seriya Matematika. 2023. T. 46. C. 35-50.</mixed-citation>
    </citation-alternatives>
   </ref>
   <ref id="B7">
    <label>7.</label>
    <citation-alternatives>
     <mixed-citation xml:lang="ru">Lempert A. A., Kazakov A. L., Le Q. M. On reserve and double covering prob-lems for the sets with non-Euclidean metrics // Yugoslav Journal of Operations Research. 2019. Vol. 29, № 1. P. 69-79.</mixed-citation>
     <mixed-citation xml:lang="en">Lempert A. A., Kazakov A. L., Le Q. M. On reserve and double covering prob-lems for the sets with non-Euclidean metrics // Yugoslav Journal of Operations Research. 2019. Vol. 29, № 1. P. 69-79.</mixed-citation>
    </citation-alternatives>
   </ref>
   <ref id="B8">
    <label>8.</label>
    <citation-alternatives>
     <mixed-citation xml:lang="ru">Грицкевич О.В., Мещеряков Н.А., Подъянольский Ю.В. Формирование оптического изображения произвольной геометрической формы на криво-линейных поверхностях вращения // Автометрия. 1997. № 2. С. 26-33.</mixed-citation>
     <mixed-citation xml:lang="en">Grickevich O.V., Mescheryakov N.A., Pod'yanol'skiy Yu.V. Formirovanie opticheskogo izobrazheniya proizvol'noy geometricheskoy formy na krivo-lineynyh poverhnostyah vrascheniya // Avtometriya. 1997. № 2. S. 26-33.</mixed-citation>
    </citation-alternatives>
   </ref>
   <ref id="B9">
    <label>9.</label>
    <citation-alternatives>
     <mixed-citation xml:lang="ru">Казаков А. Л., Лемперт А. А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемехани-ка. 2011. Т. 72, № 7. С. 50-57.</mixed-citation>
     <mixed-citation xml:lang="en">Kazakov A. L., Lempert A. A. Ob odnom podhode k resheniyu zadach optimizacii, voznikayuschih v transportnoy logistike // Avtomatika i telemehani-ka. 2011. T. 72, № 7. S. 50-57.</mixed-citation>
    </citation-alternatives>
   </ref>
  </ref-list>
 </back>
</article>
