Journal
COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS
Volume 53, Issue 11, Pages 1748-1762Publisher
PLEIADES PUBLISHING INC
DOI: 10.1134/S0965542513110080
Keywords
numerical methods for ellipse packing; packing of equal ellipses; linear models for ellipse packing; ellipse packing in rectangular domain; integer linear programming problem
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available