期刊
COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS
卷 53, 期 11, 页码 1748-1762出版社
PLEIADES PUBLISHING INC
DOI: 10.1134/S0965542513110080
关键词
numerical methods for ellipse packing; packing of equal ellipses; linear models for ellipse packing; ellipse packing in rectangular domain; integer linear programming problem
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据