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

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

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

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

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