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

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

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