关键词: 最小包围圆, 随机增量算法, 最小包围圆性质, 计算几何

Abstract: For calculating the smallest enclosing disk of a discrete set of points on the planar,
three popular algorithms, i.e. the randomized incremental algorithm, the dual decision algorithm
and the farthest point first progressive algorithm, are evaluated and an improvement of the
randomized incremental algorithm is presented. The new algorithm employs the Axis-Aligned
Bounding Boxes of the point set to optimize the initiate enclosing disk, which greatly improves
the calculating efficiency. Numerical experiments show that the farthest point first progressive
algorithm is the fastest one among the old three algorithms; the new algorithm is a fast and
deterministic one, and can be helpful to the applications in computer graphics, facility locations,
intelligent robot, and so on.

Key words: smallest enclosing disk, randomized incremental algorithm, property of smallest
enclosing disk, computational geometry