Dotcpp  >  编程教程  >  计算几何  >  简述随机增量法

简述随机增量法

点击打开在线编译器,边学边练

随机增量算法是计算几何的一个重要算法,它对理论知识要求不高,算法时间复杂度低,应用范围广大。

增量法 (Incremental Algorithm) 的思想与第一数学归纳法类似,它的本质是将一个问题化为规模刚好小一层的子问题。解决子问题后加入当前的对象。写成递归式是:

递归式

增量法形式简洁,可以应用于许多的几何题目中。

增量法往往结合随机化,可以避免最坏情况的出现。


最小圆覆盖问题

题意描述:在一个平面上有 n 个点,求一个半径最小的圆,能覆盖所有的点。

过程

假设圆O是前 i-1 个点的最小覆盖圆,加入第 i 个点,如果在圆内或边上则什么也不做。否则,新得到的最小覆盖圆肯定经过第 i 个点。

然后以第 i 个点为基础(半径为 0),重复以上过程依次加入第 j 个点,若第 j 个点在圆外,则最小覆盖圆必经过第 j 个点。

重复以上步骤。(因为最多需要三个点来确定这个最小覆盖圆,所以重复三次)

遍历完所有点之后,所得到的圆就是覆盖所有点得最小圆。


性质

时间复杂度O(n)。

空间复杂度O(n)。



知识点标签:计算几何


本文固定URL:https://www.dotcpp.com/course/1081

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)