随机增量法
介绍
随机增量算法是计算几何的一个重要算法，它对理论知识要求不高，算法时间复杂度低，应用范围广大．
增量法 (Incremental Algorithm) 的思想与第一数学归纳法类似，它的本质是将一个问题化为规模刚好小一层的子问题．解决子问题后加入当前的对象．写成递归式是：
增量法形式简洁，可以应用于许多的几何题目中．
增量法往往结合随机化，即随机增量法．
随机增量法的思路是：每次加入一个新的对象时，如果改变答案，那么局部重新计算．因此，随机增量法通常要求容易快速判断加入一个元素是否修改答案，且在随机顺序下答案改变次数的期望较少．
随机增量法常用于求解 最小圆覆盖 问题，也可以用于求解半空间交、高维凸包、随机 Delaunay 三角剖分等问题．
练习
参考资料与扩展阅读
https://www.cnblogs.com/aininot260/p/9635757.html
https://blog.csdn.net/u014609452/article/details/62039612
本页面最近更新：2026/9/19 22:55:32，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, Tiphereth-A, Catreap, GWBailang553, TianyiQ, Enter-tainer, Henry-ZHR, HeRaNO, iamtwz, ksyx, ouuan, sshwy, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用