离散点集最小包围圆算法分析与改进

摘要

本文针对平面上离散点集求取最小包围圆的问题，评述现有算法，并给出一种改进算法，称为较远点对定义初始包围圆的随机增量算法。首先对求取最小包围圆的随机增量算法，最远点优先渐近算法、对偶决策算法等三种典型算法进行概述和简要分析；然后对随机增量算法进行改进；最后，以二维区域随机点集、一维共线随机点集和共线有序点集三类数据进行实验对比。实验结果表明：最远点优先渐近算法是本文列举的三种算法中效率最高的，本文提出的改进算法是一种更快的确定性算法，并大大提高随机增量算法的时间效率，离散点集最小包围圆的快速计算在碰撞检测和机器人等领域有广泛应用。