2013年4月1日 星期一

最小圓覆蓋

好久沒有學習新東西了,今天因為剛好要用到 (poi的plot)

所以就順便學一下了,如果有敘述不清,歡迎糾正>_____<

=====================================


Lv 1. Naiwny Algorytm(樸素算法) O(n^4)


枚舉三個點,做出一個圓圈圈,看有沒有覆蓋所有的點點點點


Lv 2. Zhang Jiao(張角法) O(n^3)



       想法其實也很簡單,就是枚舉兩個點(如圖中的A, B)當圓周上的點,接下來,因為離這個圓越遠的角一定越小,所以找出在AB線段上面跟下面兩種的最小角點(也就是像圖中的C與D),如果這兩個角alpha + beta >= pi 的話,你就得到一個包含圓了(太小就變成一個怪怪的橢圓了),雖然要特別判一下,就是如果max(alpha, beta) >= pi,就可以把AB當成直徑,如果 < pi,就拿這三個點做圓(必定唯一)。

接下來就要進行大進化!

Lv 9999999. Venusaur(廟哇花) O(n)

       其實叫隨機增量法 A___A ,利用一個神定理和Random的特性,以最樸素作法少三個冪次的超神演算法。(雖然常數頗大)

神定理:假設{p1, p2 ... pi-1},形成一個最小包含圓,若pi不在這個圓內,那麼{p1, p2 ... pi}所產生的最小包含圓一定有pi在圓周上。

{p1 ~ pi-1} 產生一個最小包含圓:
加入 pi 之後(不是M_PI,只是p的第i項XDDD)
--------------------------------------------------------------------
1. pi 在圓內or圓上:爽!什麼毛都不用做
2. pi 在圓外:對於{p1 ~ pi}的最小包含圓,pi一定在圓上(依據神定理)

=====================================

至於他發生2.的這件事的機率是多少呢!因為1~i ,普通情況只會有三個點在圓上,所以機率是 3 / i !!!!!!!!!!! 接下來你輕鬆亂推廣神定理。

亂推神定理:假設{p1, p2 ... pi-1},且點 x 在圓周上,形成一個最小包含圓,若pi不在這個圓內,那麼{p1, p2 ... pi}且點 x 在圓周上,所產生的最小包含圓一定有pi在圓周上。

{p1 ~ pi-1} 且圓周上有點x,產生一個最小包含圓:
加入 pi 之後
--------------------------------------------------------------------
1. pi 在圓內or圓上:爽!什麼毛都不用做
2. pi 在圓外:對於{p1 ~ pi}且x在圓周上的最小包含圓,pi一定在圓上(依據亂推神定理)


=====================================


相同的,發生2.的機率還是3 / i 或更低。這時你已經確定有兩個點在圓周上了。
接下來,反正就再做一次亂推神定理,就有三個確定的點啦~~~~~~~~~

三個點形成一個圓~所以就結束了。

至於為什麼是O(n),請自行做點小小的計算吧。

3 則留言:

  1. 隨機增量超神奇的
    A____A

    回覆刪除
    回覆
    1. 真的超強的~
      不過你是哪位?XD

      刪除
  2. 你好,請問這個神定理:假設{p1, p2 ... pi-1},形成一個最小包含圓,若pi不在這個圓內,那麼{p1, p2 ... pi}所產生的最小包含圓一定有pi在圓周上。
    它的正確性如何證明呢?感覺並不是那麼的顯而易見。
    謝謝~

    回覆刪除