隨機(jī)增量算法

1、第1頁隨機(jī)增量算法解軼倫【摘要】隨機(jī)增量算法是計算幾何中一個重要的算法，它對理論知識要求不高，編程復(fù)雜度低，而應(yīng)用范圍卻十分廣大。本文通過兩個經(jīng)典例題，詳細(xì)闡述了本人一步一步理解隨機(jī)增量算法的過程，最后是本人對隨機(jī)增量算法的總結(jié)以及思考過程中的感悟?！娟P(guān)鍵字】增量算法隨機(jī)化計算幾何【目錄】摘要................................................................1關(guān)鍵字.....

2、.........................................................1目錄................................................................1引言................................................................2正文..........................

3、......................................2例一監(jiān)視攝像機(jī).................................................2問題描述...................................................2問題分析...................................................3算法描述........

4、...........................................5復(fù)雜度分析.................................................5例二最小外接圓.................................................6問題描述...................................................6算法一.....

5、................................................6算法二.....................................................6算法三.....................................................7總結(jié).......................................................

6、.........7參考文獻(xiàn)............................................................7附錄................................................................7第3頁輸入文件包含一個或多個房間示意圖的描述信息。每個描述信息的第一行是一一個正整數(shù)n（4＜=n＜=100），表示該房間的示意圖為一個n邊形。以下n行每行包

7、括用空格符隔開的兩個整數(shù)xy按順時針方向依次為這個n邊形的n個頂點在直角坐標(biāo)系中的的橫縱坐標(biāo)，xy的范圍在：1000至1000之間。若n等于0則表示輸入文件結(jié)束。輸出輸出對于每個房間，首先輸出一行該房間的編號信息“Room＃k：”，k按照輸入次序從1開始計數(shù)。緊接著一行是判斷結(jié)果，如果攝像機(jī)在房間中某處安置能滿足條件，輸出：“surveillanceispossible?！?，否則輸出“surveillanceisimpossible?！?/p>

8、每兩個房間的輸出結(jié)果之間用一個空行隔開。申明申明：下面的分析與算法描述中，半平面、直線、不等式、向量都可視為等價的。問題分析問題分析讀完題目給人的第一印象是求半平面相交，由于題目按順時針方向給出頂點，所以我們可以用向量來表示半平面：如圖，如果點P在邊ViVi1內(nèi)側(cè)，那么從ViVi1轉(zhuǎn)到ViP為順時針，所以它們的叉積小于等于0，于是我們可以很容易地得到每個半平面的代數(shù)形式。但如果直接做半平面這令人感覺殺雞用牛刀，因為問題只要求判斷是否存在

9、可行區(qū)域，并不要求具體解的情況，因此我們應(yīng)該考慮更簡單的方法。另一個直觀的想法是，枚舉網(wǎng)格上的點，看能否滿足不等式組，但這顯然不會是一個有效算法。上面的算法看上去“很笨”，但是會讓我們產(chǎn)生一種改進(jìn)的沖動。枚舉網(wǎng)格上的點太盲目，完全沒有利用已知條件。再來仔細(xì)分析一下問題，半平面相交最后得到的一定是個凸多邊形，而我們就是要找到一個點，這個點屬于這個凸多邊形，那么我們可不可以加強一下命題，只考慮一些特殊的點呢？顯然，凸多邊形的頂點就是一類很特