首先，我對(duì)問題進(jìn)行一下描述：
首先，我對(duì)問題進(jìn)行一下描述:
面對(duì)出自名家手臂的繪畫作品，怦然心動(dòng)的可不只是藝術(shù)愛好者，罪犯?jìng)円彩侨绱?，這類作品價(jià)值不菲，易
運(yùn)輸，而且很顯然，不愁出不了手，正是因?yàn)槿绱?，藝術(shù)畫廊必須對(duì)其所擁有的作品嚴(yán)加看管。白天，可以由值班人員擔(dān)負(fù)起看守的任務(wù)，然而晚上，這項(xiàng)工作就交到了攝像機(jī)的肩上，通常，這些攝像機(jī)都被安裝在天花板上面，繞著某個(gè)垂直的軸旋轉(zhuǎn)，由攝像機(jī)采集到的圖像，將被傳送到守夜值班室的電視屏幕上。顯然，眼睛同時(shí)要盯住的屏幕數(shù)量越少，守夜員就要輕松一點(diǎn)，因此，總是希望能夠盡可能減少攝像機(jī)的數(shù)目。還有一個(gè)好處，可以使得保安系統(tǒng)的成本更低，但是，攝像機(jī)的數(shù)目也不能太少，畫廊的每一個(gè)角落，都必須落在攝像機(jī)的視野之內(nèi)。因此，這就導(dǎo)出了我們的問題：
給定一個(gè)畫廊，需要多少臺(tái)攝像機(jī)？應(yīng)該將他們?nèi)绾蝿澐郑?/span>
解答：為了覆蓋一個(gè)簡(jiǎn)單多邊形，需要多少臺(tái)攝像機(jī)呢？顯然，這就取決于具體的多邊形。多邊形越復(fù)雜，需要的攝相機(jī)越多，但是不幸的是：“計(jì)算出特定多邊形的所需攝像機(jī)的最小數(shù)目”這一問題將是“NP-難的”
三角剖分：通過極大的一組互不相交的對(duì)角線，可以將一個(gè)多邊形分解為多個(gè)三角形，我們稱之為該多邊形的一個(gè)三角剖分。
定理1：任何的簡(jiǎn)單多邊形都存在至少一個(gè)三角剖分；若其頂點(diǎn)數(shù)為n,則他的三角剖分恰好包含n-2個(gè)三角形。