| 摘要: |
| 提出一种算法，以解决求一个最小圆包含给定点集所有点的问题.证明了这种算法的时间复杂性为O(|lg(d/R)|*n),其中R是所求的最小圆的半径,d为点集中不在圆周上但距圆周最近的点到圆周的距离. |
| 关键词: 最小圆,计算几何. |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到国家自然科学基金(No.69973028)资助. |
|
| An Algorithm for Finding the Smallest Circle Containing all Points in a Given Point Set |
|
WANG Wei,WANG Wen-ping,WANG Jia-ye
|
| Abstract: |
| To seek a smallest circle containing all the point of a given point set is an interesting problem in both practice and theory. In this paper, an algorithm of finding a smallest circle containing all the points given is presented. The time complexity of the algorithm is O(|lg(d/R)|*n), where R is the radius between the smallest circle, d is the smallest distance between the points of the set that are not on the circle and the circle. |
| Key words: Smallest circle, computational geometry. |
