簡單多邊形中兩個守衛(wèi)的max-min算法研究.pdf

1、兩個守衛(wèi)(two-guard)問題是計算幾何中的重要研究課題之一,由于很多實際問題都可以轉(zhuǎn)化為平面內(nèi)的幾何模型進(jìn)行求解,兩個守衛(wèi)的搜索區(qū)域以平面內(nèi)的簡單多邊形為模型,在它的邊沿上有一個入口s和一個出口t,兩個守衛(wèi)(two-guard)問題要求守衛(wèi)從入口s出發(fā),對多邊形區(qū)域內(nèi)的目標(biāo)(非法入侵者)進(jìn)行監(jiān)視,并將其從出口t驅(qū)逐出去。對于此類問題的探索研究,為更多實際應(yīng)用問題的解決提供了新思路和新方法,具有重要的理論意義和實際應(yīng)用價值。

2、　　 本文對簡單多邊形中兩個守衛(wèi)的max-min問題即兩個守衛(wèi)的最大可視距離達(dá)到最小的問題進(jìn)行了深入研究,對計算幾何中的相關(guān)基礎(chǔ)理論以及經(jīng)典守衛(wèi)問題進(jìn)行了論述,研究了可直掃描多邊形所具有的特性,分析討論構(gòu)成原子掃描的幾種情形以及最優(yōu)直掃描劃分為若干個原子掃描的構(gòu)造過程,并分別給出構(gòu)造關(guān)鍵掃描線段和原子掃描的方法,從而構(gòu)造得到原子掃描圖,應(yīng)用到max-min問題的求解算法中。最后,探索研究設(shè)計相應(yīng)的數(shù)據(jù)結(jié)構(gòu),用來存儲給定多邊形內(nèi)所有可能