|
This article is cited in 12 scientific papers (total in 12 papers)
Numerical optimization methods for packing equal orthogonally oriented ellipses in a rectangular domain
Sh. I. Galiev, M. S. Lisafina Kazan National Research Technological University, ul. Karla Marksa 10, Kazan, 420111, Tatarstan, Russia
Abstract:
Linear models are constructed for the numerical solution of the problem of packing the maximum possible number of equal ellipses of given size in a rectangular domain $R$. It is shown that the $l_p$ metric can be used to determine the conditions under which ellipses with mutually orthogonal major axes (orthogonally oriented ellipses) do not intersect. In $R$ a grid is constructed whose nodes generate a finite set $T$ of points. It is assumed that the centers of the ellipses can be placed only at some points of $T$. The cases are considered when the major axes of all the ellipses are parallel to the $x$ or $x$ axis or the major axes of some of the ellipses are parallel to the $x$ axis and the others, to the $y$ axis. The problems of packing equal ellipses with centers in $T$ are reduced to integer linear programming problems. A heuristic algorithm based on the linear models is proposed for solving the ellipse packing problems. Numerical results are presented that demonstrate the effectiveness of this approach.
Key words:
numerical methods for ellipse packing, packing of equal ellipses, linear models for ellipse packing, ellipse packing in rectangular domain, integer linear programming problem.
Received: 11.02.2013 Revised: 06.05.2013
Citation:
Sh. I. Galiev, M. S. Lisafina, “Numerical optimization methods for packing equal orthogonally oriented ellipses in a rectangular domain”, Zh. Vychisl. Mat. Mat. Fiz., 53:11 (2013), 1923–1938; Comput. Math. Math. Phys., 53:11 (2013), 1748–1762
Linking options:
https://www.mathnet.ru/eng/zvmmf9951 https://www.mathnet.ru/eng/zvmmf/v53/i11/p1923
|
Statistics & downloads: |
Abstract page: | 316 | Full-text PDF : | 108 | References: | 59 | First page: | 25 |
|