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

Investigation to rectangle triangulation problem

作　　者：王瑞民[1] 何大华[2] 裴利军[3] 

机构地区：[1]郑州大学信息工程学院,郑州450001 [2]华中光电技术研究所,武汉430073 [3]郑州大学数学系,郑州450001

出　　处：《计算机工程与应用》2008年第33期22-24,共3页Computer Engineering and Applications

基　　金：国家自然科学基金No.10702065~~

摘　　要：给出了矩形的三角形划分问题的定义,该问题是三角形Packing问题的一个特例,证明了该问题是NP完全的,并给出了该问题有解的一个必要条件。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.

关 键 词：三角形PACKING问题 矩形的三角形划分问题 NP完全 格局 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]