兩個守衛(wèi)問題的最優(yōu)掃描算法研究與實現(xiàn).pdf

1、Two-guard問題是計算幾何學領域的熱點問題，研究該問題，不僅涉及到求解多邊形的可視性、Fréchet距離、最短路徑等理論問題的技術方法與研究成果，而且由于Two-guard問題也是很多實際應用問題的抽象模型使得該問題的研究具有很好的實際應用背景，因此，研究該問題，不僅具有理論意義，而且具有很大的實際應用價值。
　　本文在論述畫廊問題、Fréchet距離問題、簡單多邊形及其可視性、min-sum與min-max量度標準及含義的

2、基礎上，對兩個守衛(wèi)可掃描簡單多邊形的幾何結構極其特性，做了較為深入的研究，分析了可掃描簡單多邊形的直掃描和反掃描的掃描方式、掃描規(guī)則及其掃描方案的構成，詳細論述了min-sum度量標準下的掃描規(guī)則與射線段圖與min-max度量下的關鍵掃描線段與原子掃描圖的構造過程與構造技術，運用圖論的技術方法，將幾何搜索問題轉化為圖的遍歷問題，分別設計出了時間復雜度為O(n2)的min-sum度量標準下的最優(yōu)搜索策略和min-max度量標準下的最優(yōu)搜索