Numerical optimization methods for packing equal orthogonally oriented ellipses in a rectangular domain

Sh. I. Galiev ; M. S. Lisafina

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 53 (2013) no. 11, pp. 1923-1938

Résumé

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.