隨機(jī)增量算法

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

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

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

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

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

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

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

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

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