From 214f6a7e4c71e03e036231aec9580179d108d572 Mon Sep 17 00:00:00 2001 From: Xeonacid Date: Mon, 27 May 2019 12:47:15 +0800 Subject: [PATCH] Update random-incremental.md --- docs/geometry/random-incremental.md | 18 ++++++++++-------- 1 file changed, 10 insertions(+), 8 deletions(-) diff --git a/docs/geometry/random-incremental.md b/docs/geometry/random-incremental.md index 6610b778..8ac3cb1e 100644 --- a/docs/geometry/random-incremental.md +++ b/docs/geometry/random-incremental.md @@ -2,27 +2,29 @@ 随机增量算法是计算几何的一个重要算法,它对理论知识要求不高,算法时间复杂度低,应用范围广大。 -增量法($Incremental\ Algorithm$)的思想与第一数学归纳法类似,它的本质是将一个问题化为规模刚好小一层的子问题。解决子问题后加入当前的对象。写成递归式是: +增量法 (Incremental Algorithm) 的思想与第一数学归纳法类似,它的本质是将一个问题化为规模刚好小一层的子问题。解决子问题后加入当前的对象。写成递归式是: + $$ T(n)=T(n-1)+g(n) $$ + 增量法形式简洁,可以应用于许多的几何题目中。 增量法往往结合随机化,可以避免最坏情况的出现。 ## 最小圆覆盖问题 -#### 题意描述 +### 题意描述 -在一个平面上有$n$个点,求一个半径最小的圆,能覆盖所有的点。 +在一个平面上有 $n$ 个点,求一个半径最小的圆,能覆盖所有的点。 -#### 算法 +### 算法 -假设圆$O$是前$i-1$个点得最小覆盖圆,加入第i个点,如果在圆内或边上则什么也不做。否,新得到的最小覆盖圆肯定经过第$i$个点 +假设圆 $O$ 是前 $i-1$ 个点得最小覆盖圆,加入第 $i$ 个点,如果在圆内或边上则什么也不做。否,新得到的最小覆盖圆肯定经过第 $i$ 个点。 -然后以第$i$个点为基础(半径为$0$),重复以上过程依次加入第$j$个点,若第$j$个点在圆外,则最小覆盖圆必经过第$j$个点。 +然后以第 $i$ 个点为基础(半径为 $0$),重复以上过程依次加入第 $j$ 个点,若第 $j$ 个点在圆外,则最小覆盖圆必经过第 $j$ 个点。 -重复以上步骤(因为最多需要三个点来确定这个最小覆盖圆,所以重复三次) +重复以上步骤。(因为最多需要三个点来确定这个最小覆盖圆,所以重复三次) 遍历完所有点之后,所得到的圆就是覆盖所有点得最小圆。 @@ -30,7 +32,7 @@ $$ **空间复杂度** $O(n)$ -#### 代码 +### 代码 ```cpp #include -- 2.11.0