A Heuristic Algorithm for Solving Triangle Packing Problem

Ruimin Wang, Yuqiang Luo, Jianqiang Dong, Shuai Liu and Xiaozhuo Qi

Discrete Dynamics in Nature and Society, 2013, vol. 2013, 1-7

Abstract:

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.

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/DDNS/2013/686845.pdf (application/pdf)
http://downloads.hindawi.com/journals/DDNS/2013/686845.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnddns:686845

DOI: 10.1155/2013/686845

Access Statistics for this article

More articles in Discrete Dynamics in Nature and Society from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().