| 覆盖平面上给定点集的最小凸多边形的算法 |
| |
| 引用本文： | 许如初,宋恩民,陈卫东,董向锋. 覆盖平面上给定点集的最小凸多边形的算法[J]. 华中科技大学学报(自然科学版), 1996, 0(6) |
| |
| 作者姓名： | 许如初 宋恩民 陈卫东 董向锋 |
| |
| 基金项目： | 国家自然科学基金（19331050）和华中理工大学青年科研基金资助项目 |
| |
| 摘 要： | 研究求覆盖平面上给定的若干个点的最小凸多边形的算法．给出了两种算法，讨论了算法的基本思想，描述了算法步骤，得出了算法的时间复杂度．结果表明，算法的平均计算时间复杂度为平面上给定点的数量的线性函数，即为Ο（ｎｍ），在最坏情况下可为Ο（ｍ２）
|
| 关 键 词： | 最小覆盖问题；计算时间复杂度；算法 |
Algorithms for a Minimal Convex Polygon to Cover Given Points on 2 Dimensional Space |
| |
| Abstract: | Two algorithms for a minimal convex polygon to cover given points on 2 dimensional space are proposed.The basic idea is discussed and the procedure described.The results show that the complexity of the average computing time of the algorithms is a linear function of the number of the given points. |
| |
| Keywords: | minimal covering complexity of computing time algorithm |
|
