矩形条覆盖问题的贪心算法  

A Greedy Algorithm for Rectangle Cover Problem

作　　者：王晓东[1] 高磊[1] 范长青[1] 

机构地区：[1]福州大学计算机科学与技术系,福建福州350002

出　　处：《福州大学学报（自然科学版）》2000年第2期1-5,共5页Journal of Fuzhou University(Natural Science Edition)

基　　金：国家重大基础研究项目!(G19980 30 6 0 0 );福建省自然科学基金资助项目!(F9810 0 9-JS - 98- 1)

摘　　要：讨论了计算几何学中的矩形条覆盖问题 ,提出解决该问题的一个有效算法 ,并对提出的算法进行了分析 .This paper discusses the problem of covering an ordered point set by a sequence of rectangles with minimum width in the area of computational geometry. An efficient algorithm is presented and analyzed.

关 键 词：折线 凸壳 矩形条覆盖问题 贪心算法 计算几何学 

分 类 号：O3-39[理学—力学] O302