An algorithm of packing congruent circles in a multiply connected set with non-Euclidean metrics


  • A.L. Kazakov Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)
  • A.A. Lempert Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)
  • H.L. Nguyen Irkutsk National Research Technical University



optimal packing of circles, optical-geometric approach, non-Euclidean space, multiply connected domain, numerical method, computational experiment


The problem of optimal packing of congruent circles in a bounded set (a container) in a two-dimensional metric space is considered. It is required to find an arrangement of circles in the container such that these circles occupy the largest area of the container as possible. In the case when the space is Euclidean, this problem is well known, but the case of non-Euclidean metrics is studied much worse. However, there are some applied problems leading us to the use of special non-Euclidean metrics. For example, such a situation appears in the infrastructure logistics. Here we consider the optimal packing problem in the case when the container is simply or multiply connected. A special algorithm based on the optical-geometric approach is proposed and implemented. The results of numerical experiments are discussed.


A.L. Kazakov

A.A. Lempert

H.L. Nguyen



How to Cite

Kazakov A.L., Lempert A.A., Nguyen H.L. An Algorithm of Packing Congruent Circles in a Multiply Connected Set With Non-Euclidean Metrics // Numerical methods and programming. 2016. 17. 177-188. doi 10.26089/NumMet.v17r216



Section 1. Numerical methods and applications