A Heuristic Algorithm for Solving Triangle Packing Problem
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 p...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2013/686845 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832561196165758976 |
|---|---|
| author | Ruimin Wang Yuqiang Luo Jianqiang Dong Shuai Liu Xiaozhuo Qi |
| author_facet | Ruimin Wang Yuqiang Luo Jianqiang Dong Shuai Liu Xiaozhuo Qi |
| author_sort | Ruimin Wang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-0627b31cc0f24028aec7eca562ff310f |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-0627b31cc0f24028aec7eca562ff310f2025-02-03T01:25:40ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2013-01-01201310.1155/2013/686845686845A Heuristic Algorithm for Solving Triangle Packing ProblemRuimin Wang0Yuqiang Luo1Jianqiang Dong2Shuai Liu3Xiaozhuo Qi4School of Information Engineering, Zhengzhou University, Zhengzhou 450001, ChinaInformatization Office, University of Shanghai for Science and Technology, Shanghai 200093, ChinaZhengzhou Xinda Jiean Information Technology Co., Ltd., Zhengzhou 450002, ChinaCollege of Science, University of Shanghai for Science and Technology, Shanghai 200093, China95107 Troops, Guangzhou 510500, ChinaThe 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.http://dx.doi.org/10.1155/2013/686845 |
| spellingShingle | Ruimin Wang Yuqiang Luo Jianqiang Dong Shuai Liu Xiaozhuo Qi A Heuristic Algorithm for Solving Triangle Packing Problem Discrete Dynamics in Nature and Society |
| title | A Heuristic Algorithm for Solving Triangle Packing Problem |
| title_full | A Heuristic Algorithm for Solving Triangle Packing Problem |
| title_fullStr | A Heuristic Algorithm for Solving Triangle Packing Problem |
| title_full_unstemmed | A Heuristic Algorithm for Solving Triangle Packing Problem |
| title_short | A Heuristic Algorithm for Solving Triangle Packing Problem |
| title_sort | heuristic algorithm for solving triangle packing problem |
| url | http://dx.doi.org/10.1155/2013/686845 |
| work_keys_str_mv | AT ruiminwang aheuristicalgorithmforsolvingtrianglepackingproblem AT yuqiangluo aheuristicalgorithmforsolvingtrianglepackingproblem AT jianqiangdong aheuristicalgorithmforsolvingtrianglepackingproblem AT shuailiu aheuristicalgorithmforsolvingtrianglepackingproblem AT xiaozhuoqi aheuristicalgorithmforsolvingtrianglepackingproblem AT ruiminwang heuristicalgorithmforsolvingtrianglepackingproblem AT yuqiangluo heuristicalgorithmforsolvingtrianglepackingproblem AT jianqiangdong heuristicalgorithmforsolvingtrianglepackingproblem AT shuailiu heuristicalgorithmforsolvingtrianglepackingproblem AT xiaozhuoqi heuristicalgorithmforsolvingtrianglepackingproblem |