Open AccessAn algorithm for packing balls of two types in a three-dimensional set with a non-Euclidean metric
Author(s) -
А. Л. Казаков,
A. A. Lempert,
Ч.Т. Та
Publication year - 2020
Publication title -
vyčislitelʹnye metody i programmirovanie
Language(s) - English
Resource type - Journals
eISSN - 1726-3522
pISSN - 0507-5386
DOI - 10.26089/nummet.v21r213
Subject(s) - metric (unit) , dynamical billiards , mathematics , bounded function , euclidean geometry , euclidean space , set (abstract data type) , euclidean distance , euclidean distance matrix , radius , metric space , algorithm , combinatorics , discrete mathematics , computer science , mathematical analysis , geometry , operations management , computer security , economics , programming language
Рассматривается задача упаковки шаров двух типов в замкнутое ограниченное множество в трехмерном пространстве как с евклидовой, так и со специальной неевклидовой метрикой. Требуется максимизировать радиус шаров при известном количестве шаров каждого типа и заданном отношении между радиусами. Предложен вычислительный алгоритм, основанный на комбинации метода бильярдного моделирования и оптико-геометрического подхода, базирующегося на фундаментальных физических принципах Ферма и Гюйгенса. Приведены результаты вычислительного эксперимента. The problem of packing balls of two types into a closed bounded set in three-dimensional space with the Euclidean metric and a special non-Euclidean metric. It is required to maximize the radius of the balls for a given number of balls of each type and a known ratio of radii. We propose a computational algorithm based on a combination of the billiard modeling method and the optical-geometric approach employing the fundamental physical principles of Fermat and Huygens. The results of numerical experiments are discussed.