УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ
на главную написать письмо карта сайта


јвтор:   азаков ј.Ћ., Ћемперт ј.ј., Ће  .ћ.
Ќазвание:  ќ задачах построени€ многократных покрытий и†упаковок в двумерном неевклидовом пространстве
¬ыпуск:  81
–убрика:  —истемный анализ
√од:  2019
Ѕиблиографи€:   азаков ј.Ћ., Ћемперт ј.ј., Ће  .ћ. ќ задачах построени€ многократных покрытий и†упаковок в двумерном неевклидовом пространстве // ”правление большими системами. ¬ып. 81. ћ.: »ѕ” –јЌ, 2019. —.6-25. DOI: https://doi.org/10.25728/ubs.2019.81.1
 лючевые слова:  многократное покрытие множества, многократна€ упаковка кругов, неевклидова метрика, вычислительный алгоритм, оптико-геометрический подход, диаграмма ¬ороного, численный эксперимент
 лючевые слова (англ.):  multiple packing, equal circles, non-Euclidean metric, algorithm, Voronoi -- Dirichlet diagram, Fermat and Huygens principles
јннотаци€:  —тать€ посв€щена изучению двух содержательных задач вычислительной геометрии: задачи построени€ оптимальных многократных покрытий кругами замкнутого ограниченного множества в двумерном метрическом пространстве и аналогичной задачи упаковки кругов. ¬ обоих случа€х число кругов фиксировано. ¬ первом случае целью €вл€етс€ минимизаци€, а во втором --- максимизаци€ радиуса кругов. –ассматриваема€ метрика, вообще говор€, неевклидова. »сточником такой постановки €вл€етс€ транспортна€ логистика, где встречаютс€ задачи, в которых рассто€ние между объектами необходимо заменить минимальным временем перемещени€ между ними, при этом искомый оптимум в силу особенностей местности далеко не всегда достигаетс€ при движении по пр€мой линии. ƒл€ решени€ задач предложены вычислительные алгоритмы, которые основаны на применении оптико-геометрического подхода, базирующегос€ на принципах геометрической оптики ‘ерма и √юйгенса, и методе K-средних.  лючевым этапом работы в обоих случа€х €вл€етс€ построение обобщенной диаграммы ¬ороного пор€дка k, кажда€ €чейка которой при фиксированном наборе из n центроидов включает в себ€ точки, расположенные ближе к некоторым k центроидам, чем к оставшимс€ n-k. ѕри этом, в отличие от классической диаграммы ¬ороного, здесь €чейки могут пересекатьс€. ѕроведены вычислительные эксперименты, выполнены обсуждение и интерпретаци€ их результатов.
јннотаци€ (англ.):  The article is devoted to the study of two significant problems of computational geometry. The first one is the multiple circle covering problem for a closed bounded set in a two-dimensional metric space, and the second one is the multiple circle packing problem. In the first case, the objective is to minimize the radius of the circles, in the second one is to maximize it. In both cases, the number of circles k is given. The considered metric is generally non-Euclidean. The source of such a statement is tasks from transport logistics, where the distance between objects is necessary to be replaced with a minimum time to travel between them. And optimum is not always achieved with straight line moving due to the terrain or urban features. We propose computational algorithms to solve these problems. They include the joint use of an optical-geometric approach based on the principles of Fermat and Huygens and the K-means method. The key step is to construct a generalized k-order Voronoi diagram. Each Voronoi cell with a fixed set of n centroids includes points, which are closer to some k centroids than to the remaining n-k . The cells can intersect each other. Computational experiments are carried out.

¬ формате PDF
ќбсудить статью в »нтернет-конференции по проблемам управлени€

ѕросмотров: 68, загрузок: 13, за мес€ц: 10.

Ќазад

»ѕ” –јЌ © 2007. ¬се права защищены