求一个包含点集所有点的最小圆的算法

被引：23

作者：

汪卫

王文平

汪嘉业

机构：

[1] 复旦大学计算机系!上海

[2] 香港大学计算机系!香港

[3] 山东大学计算机系!济南

来源：

软件学报 | 2000年 / 09期

关键词：

最小圆; 计算几何;

D O I：

10.13328/j.cnki.jos.2000.09.014

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

提出一种算法 ,以解决求一个最小圆包含给定点集所有点的问题 .证明了这种算法的时间复杂性为O( |lg( d/R) |* n) ,其中 R是所求的最小圆的半径 ,d为点集中不在圆周上但距圆周最近的点到圆周的距离 .

引用

收藏

页码：1237 / 1240

页数：4

相关论文

共 5 条

[1]

Computational Geometry. Toussaint G T. .

[2]

The Design and Analysis of Spatial Data Structure. Samet H. . 1989

[3]

Computational Geometry in C. O’Rourke J. . 1994

[4]

Computational Geometry:An Introduction. Preparata F P,Shamos MI. . 1985

[5]

Application of Spatial Data Structure. Samet H. . 1989