###
DOI:
Journal of Software:2000.11(9):1237-1240

求一个包含点集所有点的最小圆的算法
汪卫,王文平,汪嘉业
(复旦大学计算机系,上海,200433;香港大学计算机系,香港;山东大学计算机系,济南,250100)
An Algorithm for Finding the Smallest Circle Containing all Points in a Given Point Set
WANG Wei,WANG Wen-ping,WANG Jia-ye
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3421   Download 3909
Received:February 28, 2000    Revised:May 12, 2000
> 中文摘要: 提出一种算法,以解决求一个最小圆包含给定点集所有点的问题.证明了这种算法的时间复杂性为O(|lg(d/R)|*n),其中R是所求的最小圆的半径,d为点集中不在圆周上但距圆周最近的点到圆周的距离.
中文关键词: 最小圆,计算几何.
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.
文章编号:     中图分类号:    文献标志码:
基金项目:本文研究得到国家自然科学基金(No.69973028)资助. 本文研究得到国家自然科学基金(No.69973028)资助.
Foundation items:
Reference text:

汪卫,王文平,汪嘉业.求一个包含点集所有点的最小圆的算法.软件学报,2000,11(9):1237-1240

WANG Wei,WANG Wen-ping,WANG Jia-ye.An Algorithm for Finding the Smallest Circle Containing all Points in a Given Point Set.Journal of Software,2000,11(9):1237-1240