%0 Journal Article
%T A Heuristic Algorithm for Solving Triangle Packing Problem
%A Ruimin Wang
%A Yuqiang Luo
%A Jianqiang Dong
%A Shuai Liu
%A Xiaozhuo Qi
%J Discrete Dynamics in Nature and Society
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/686845
%X The research on the triangle packing problem has important theoretic significance, which has broad application prospects in material processing, network resource optimization, and so forth. Generally speaking, the orientation of the triangle should be limited in advance, since the triangle packing problem is NP-hard and has continuous properties. For example, the polygon is not allowed to rotate; then, the approximate solution can be obtained by optimization method. This paper studies the triangle packing problem by a new kind of method. Such concepts as angle region, corner-occupying action, corner-occupying strategy, and edge-conjoining strategy are presented in this paper. In addition, an edge-conjoining and corner-occupying algorithm is designed, which is to obtain an approximate solution. It is demonstrated that the proposed algorithm is highly efficient, and by the time complexity analysis and the analogue experiment result is found. 1. Introduction Solving NP-hard problems is always the bottleneck task for computer science and techniques. However, in recent years, many research results have indicated that there is no a complete, accurate, and fast solving algorithm for this kind of problem at all. People tend to focus on searching for a quick and practical approximation algorithm; see, for example, [1]. Triangle packing problem is that given a known length and width of rectangle empty container and N triangles of definite size and shape; namely, the three sides of a triangle are known, and the question is whether the N triangles can be placed into the rectangle container. If we can, then give position and orientation of each triangle in the rectangle. If no, give a negative answer to this problem. Since triangle in the plane can be continuously translated and rotated, there are infinite numbers of placements which are detrimental to solve the problem. And so the placement should be limited always. The strategy in [2] is only to allow a polygon to be rotated, but not to be translated, which translates the polygon packing problem to NP-complete problem. Triangular packing problem is a special case of a polygon packing problem but is still NP-hard. For now, there is no a quick and complete solving algorithm, and the heuristic method is still an ordinary method; see, for example, [3¨C7] and references therein. In this paper, a edge-conjoining and corner-occupying algorithm that is a quick and approximate method is designed based on the angle region-filling strategy. This paper has special significance for polygon packing problem, network resource
%U http://www.hindawi.com/journals/ddns/2013/686845/