動(dòng)態(tài)規(guī)劃加速算法和輪廓探測(cè)算法.pdf

1、指導(dǎo)小組成員RudolfFleischer教授MordecaiGolin教授動(dòng)態(tài)規(guī)劃加速算法和輪廓探測(cè)算法在本文的第二部分中我們提出了幾何探測(cè)領(lǐng)域的一個(gè)新的問題一一輪廓探測(cè)(CameraProbe)問題：假設(shè)在一個(gè)半徑為1的圓內(nèi)放置了一個(gè)未知凸多邊形，輪廓探測(cè)研究的問題就是至少需要在圓周上放置多少個(gè)探測(cè)儀器才能保證任意形狀、任意放置的凸多邊形可以被重構(gòu)出來以及至多需要在圓周上放置多少個(gè)探測(cè)儀器就能保證任意形狀、任意放置的凸多邊形可以被重

2、構(gòu)出來。這個(gè)理論模型的提出是基于我們參與的一個(gè)“863”項(xiàng)目，其中一個(gè)問題是要通過位置固定的探測(cè)儀器來重構(gòu)出未知物體的位置、形狀。幾何探測(cè)正是研究這類問題的領(lǐng)域。幾何探測(cè)最早mCole和Yap在1987年提出了手指探測(cè)的模型而引入了計(jì)算幾何學(xué)中，之后各種幾何探測(cè)，包括Greschak等人提出的超平面探測(cè)，Rao等人提出的側(cè)影探測(cè)，Skiena等人提出的X光線探測(cè)等被人們廣泛研究。但這些模型都要求探測(cè)儀器的位置是不固定的，即下次探測(cè)的方向

3、和儀器放置位置可以根據(jù)之前探測(cè)結(jié)果來決定。而我們的輪廓探測(cè)模型可以適用于探測(cè)儀器事先固定好的環(huán)境下。此外，不同于其它的幾何探測(cè)問題中所需要的探測(cè)次數(shù)一般都與物體的頂點(diǎn)數(shù)有關(guān)，在我們的輪廓探測(cè)中，所需要的探測(cè)儀器數(shù)量取決于未知凸多邊形的最大內(nèi)角值a。在二維通常情況下，即任意兩個(gè)探測(cè)儀器的探測(cè)線都不重合時(shí)，我們證明了最優(yōu)解需要f熹1個(gè)探側(cè)儀器；否則在任意情況下，我們證明了至多需要『蘭]個(gè)探測(cè)儀器就能夠重構(gòu)出圓內(nèi)最大內(nèi)角不超過Q的任意凸多邊形

4、。在三維情況下，當(dāng)未知凸多面體位于一個(gè)球的內(nèi)部，所有的探測(cè)儀器放置在球面上時(shí)，我們需要的探側(cè)儀器的數(shù)量?jī)H取決于未知凸多面體內(nèi)的最大面面角的值。通過分析未知凸多面體的一個(gè)頂點(diǎn)被探測(cè)到的特性，以及結(jié)合Hardin等人的球面覆蓋理論，我們證明了對(duì)于最大面面角不超過＆的凸多面體，至多只需要(面1而30丌)個(gè)探測(cè)儀器就可以重構(gòu)出球內(nèi)任意放置、任意形狀的未知凸多面體。但是，在三維的情況下，以上的結(jié)論還有改進(jìn)的空間，針對(duì)不同探測(cè)儀器個(gè)數(shù)帶來的不同放置