多邊形監(jiān)視問題的求解算法研究.pdf

1、分類號UDC密級單位代碼10151多邊形監(jiān)視問題的求解算法研究王巖指導(dǎo)教師蔣波職稱教授學(xué)位授予單位大連海事大學(xué)申請學(xué)位級別工學(xué)碩士學(xué)科與專業(yè)計(jì)算機(jī)軟件與理論論文完成日期2008年5月論文答辯日期2008年6月答辯委員會(huì)主席中文摘要摘要隨著人們對安全監(jiān)視需求的增加，如何有效地設(shè)置和使用監(jiān)視器成為關(guān)注的焦點(diǎn)。本文將計(jì)算幾何中一類基于可視性和最優(yōu)化的lb]題定義為多邊形監(jiān)視問題，并針對如何求解這類問題進(jìn)行了較為深入的研究。多邊形監(jiān)視問題由多個(gè)

2、問題組成，根據(jù)監(jiān)視工具(守衛(wèi)、巡視員)的不同可以具體為畫廊問題，最短巡視員路徑問題，m一巡視員路徑問題等。多邊形監(jiān)視問題的求解過程會(huì)涉及大量的計(jì)算幾何相關(guān)知識，本文首先對計(jì)算幾何基本問題進(jìn)行了分析和研究。隨后對畫廊問題以及最短巡視員路徑問題的現(xiàn)有求解算法的計(jì)算復(fù)雜度及近似程度進(jìn)行了歸納，具體分析了幾個(gè)典型算法的算法描述和計(jì)算復(fù)雜度。最后，針對畫廊問題中的頂點(diǎn)守衛(wèi)情形，給出了時(shí)間復(fù)雜度均為。(n尸)的基于內(nèi)角大小的求解算法和基于填補(bǔ)技術(shù)的