计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (33): 22-24.DOI: 10.3778/j.issn.1002-8331.2008.33.006

• 博士论坛 • 上一篇    下一篇

矩形的三角形划分问题研究

王瑞民1,何大华2,裴利军3   

  1. 1.郑州大学 信息工程学院,郑州 450001
    2.华中光电技术研究所,武汉 430073
    3.郑州大学 数学系,郑州 450001
  • 收稿日期:2008-07-28 修回日期:2008-09-02 出版日期:2008-11-21 发布日期:2008-11-21
  • 通讯作者: 王瑞民

Investigation to rectangle triangulation problem

WANG Rui-min1,HE Da-hua2,PEI Li-jun3   

  1. 1.School of Information Engineering,Zhengzhou University,Zhengzhou 450001,China
    2.Huazhong Institute of Electro-Optics Technology,Wuhan 430073,China
    3.Department of Mathematics,Zhengzhou University,Zhengzhou 450001,China
  • Received:2008-07-28 Revised:2008-09-02 Online:2008-11-21 Published:2008-11-21
  • Contact: WANG Rui-min

摘要: 给出了矩形的三角形划分问题的定义,该问题是三角形Packing问题的一个特例,证明了该问题是NP完全的,并给出了该问题有解的一个必要条件。

关键词: 三角形Packing问题, 矩形的三角形划分问题, NP完全, 格局

Abstract: The problem called rectangle triangulation problem which is a special case of triangle packing problem is proposed and proved to be NP complete,a necessary condition that ensures the problem have a solution is given.

Key words: triangle packing problem, rectangle triangulation problem, NP complete, configuration