关键词: 最小包围球, 随机增量算法, 随机点组-重算最远点算法

Abstract: The minimum enclosing ball (MEB) of discrete point set in the 3D space has been widely
used in many fields, such as collision detection, computational geometry, pattern recognition and so
on. In order to better understand and construct MEB, its character is analyzed firstly. After analyzing
the classical randomized incremental algorithm, we propose two strategies to improve time efficiency.
One strategy is to construct a bigger initial enclosing ball and another strategy is to decrease the
number of updating MEB. Based on the second strategy, a new algorithm called random point
group-recalculation farthest point is proposed. Multi-group experimental results, whose data are both
randomly generated by computer and realistic 3D model sampling, show that the random point
group-recalculation farthest point algorithm can effectively improve the time efficiency compared
with the classical algorithms.

Key words: minimum enclosing ball, randomized incremental algorithm, random point grouprecalculation
farthest point