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

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 y 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.