随机增量法
引入
随机增量算法是计算几何的一个重要算法，它对理论知识要求不高，算法时间复杂度低，应用范围广大．
增量法 (Incremental Algorithm) 的思想与第一数学归纳法类似，它的本质是将一个问题化为规模刚好小一层的子问题．解决子问题后加入当前的对象．写成递归式是：
𝑇(𝑛)=𝑇(𝑛−1)+𝑔(𝑛)T(n)=T(n−1)+g(n)
增量法形式简洁，可以应用于许多的几何题目中．
增量法往往结合随机化，可以避免最坏情况的出现．
最小圆覆盖问题
题意描述
在一个平面上有 𝑛n 个点，求一个半径最小的圆，能覆盖所有的点．
过程
假设圆 𝑂O 是前 𝑖 −1i−1 个点的最小覆盖圆，加入第 𝑖i 个点，如果在圆内或边上则什么也不做．否则，新得到的最小覆盖圆肯定经过第 𝑖i 个点．
然后以第 𝑖i 个点为基础（半径为 00），重复以上过程依次加入第 𝑗j 个点，若第 𝑗j 个点在圆外，则最小覆盖圆必经过第 𝑗j 个点．
重复以上步骤．（因为最多需要三个点来确定这个最小覆盖圆，所以重复三次）
遍历完所有点之后，所得到的圆就是覆盖所有点得最小圆．
性质
时间复杂度 𝑂(𝑛)O(n)，证明详见参考资料．
空间复杂度 𝑂(𝑛)O(n)
实现
代码实现
---|---
## 练习
[最小圆覆盖](https://www.luogu.com.cn/problem/P1742)
[「HNOI2012」射箭](https://www.luogu.com.cn/problem/P3222)
[CodeForces 442E](https://codeforces.com/problemset/problem/442/E)
## 参考资料与扩展阅读
[随机增量算法 - 解轶伦](https://github.com/hzwer/shareOI/blob/master/%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95/%E9%9A%8F%E6%9C%BA%E5%A2%9E%E9%87%8F%E7%AE%97%E6%B3%95_%E8%A7%A3%E8%BD%B6%E4%BC%A6.pdf)
<https://www.cnblogs.com/aininot260/p/9635757.html>
<https://www.cise.ufl.edu/~sitharam/COURSES/CG/kreveldnbhd.pdf>
<https://blog.csdn.net/u014609452/article/details/62039612>
* * *
> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/geometry/random-incremental.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/geometry/random-incremental.md "edit.link.title")
> __本页面贡献者：[Ir1d](https://github.com/Ir1d), [Catreap](https://github.com/Catreap), [TianyiQ](https://github.com/TianyiQ), [Tiphereth-A](https://github.com/Tiphereth-A), [Enter-tainer](https://github.com/Enter-tainer), [Henry-ZHR](https://github.com/Henry-ZHR), [HeRaNO](https://github.com/HeRaNO), [iamtwz](https://github.com/iamtwz), [ksyx](https://github.com/ksyx), [ouuan](https://github.com/ouuan), [sshwy](https://github.com/sshwy), [Xeonacid](https://github.com/Xeonacid)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用