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

Authors

  • 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) https://orcid.org/0000-0001-9562-7903
  • H.L. Nguyen Irkutsk National Research Technical University

DOI:

https://doi.org/10.26089/NumMet.v17r216

Keywords:

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

Abstract

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.

Authors

A.L. Kazakov

A.A. Lempert

H.L. Nguyen

Published

2016-05-03

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

Issue

Section

Section 1. Numerical methods and applications