在这篇论文中,我们详细地研究了动态规划加速领域和几何探测领域的一些算法设计问题。在图像处理,语音识别,网络路由选择以及其它数学,计算机,计算生物领域的很多问题都可以用递归公式表示出来,从而用动态规划的方法来解决。而当这些公式又具有一些特殊的性质时,例如凸性或凹性时,我们可以进一步降低这些算法的时间复杂度。而凸性或者凹性在很多实际的问题中也是普遍存在的。在论文的第一部分中,我们讨论了对以下递归式进行动态规划加速的算法：其中Dr的值由C[1],C[2],...,C[r-1]的值所决定,Li是一个非递减函数,而g是一个给定的“失效”函数。以上的动态规划公式由于在很多领域都有应用所以已经被广泛地研究过。在通常情况下,要计算C[n]的值需要O(n2)的时间复杂度,但是当g为凸函数或凹函数,或是分段的凸／凹函数时,很多论文都证明这个问题的时间复杂度可以降低O(na(n)),在某些情况下,甚至可以达到线性的时间复杂度。其中α(n)也就是逆阿克曼函数(Inverse Ackernman function),是一个递增极其缓慢的函数,但所有时间复杂度包含了这个函数的算法都非常复杂,以至于难以理解和实现。而在本文中,我们会介绍一个简单的,新的几何方法,使得我们算法的时间复杂度可以消去逆阿克曼函数这个参数。我们的算法主要是把动态规划的公式转化为几何学中求解下包络(lower envelope)的问题,通过这种转换,不仅整个算法的时间复杂度可以降低至线性,而且相比之前的算法,尤其是当g为凸函数的情况下,更简单且容易实现。此外我们把这一方法做了进一步扩展,使其可以应用到当函数g由分段的凸函数或凹函数组成的情况下,假设函数g一共分成了k段,我们只需要O(nk)的时间复杂度,之前这类问题的最好算法是Eppstein给出的O(nka(n/k))的算法,且该算法只能应用在Li=i情况下。在本文的第二部分中我们提出了几何探测领域的一个新的问题——轮廓探钡(Camera Probe)问题：假设在一个半径为1的圆内放置了一个未知凸多边形,轮廓探测研究的问题就是至少需要在圆周上放置多少个探测仪器才能保证任意形状、任意放置的凸多边形可以被重构出来以及至多需要在圆周上放置多少个探测仪器就能保证任意形状、任意放置的凸多边形可以被重构出来。这个理论模型的提出是基于我们参与的一个“863”项目,其中一个问题是要通过位置固定的探测仪器来重构出未知物体的位置、形状。几何探测正是研究这类问题的领域。几何探测最早由Cole和Yap在1987年提出了手指探测的模型而引入了计算几何学中,之后各种几何探测,包括Greschak等人提出的超平面探测,Rao等人提出的侧影探测,Skien等人提出的x-光线探测等被人们广泛研究。但这些模型都要求探测仪器的位置是不固定的,即下次探测的方向和仪器放置位置可以根据之前探测结果来决定。而我们的轮廓探测模型可以适用于探测仪器事先固定好的环境下。此外,不同于其它的几何探测问题中所需要的探测次数一般都与物体的顶点数有关,在我们的轮廓探测中,所需要的探测仪器数量取决于未知凸多边形的最大内角值α。在二维通常情况下,即任意两个探测仪器的探测线都不重合时,我们证明了最优解需要[3π/π-α]个探侧仪器；否则在任意情况下,我们证明了至多需要[4π/π-α]个探测仪器就能够重构出圆内最大内角不超过α的任意凸多边形。在三维情况下,当未知凸多面体位于一个球的内部,所有的探测仪器放置在球面上时,我们需要的探侧仪器的数量仅取决于未知凸多面体内的最大面面角的值。通过分析未知凸多面体的一个顶点被探测到的特性,以及结合Hardin等人的球面覆盖理论,我们证明了对于最大面面角不超过α的凸多面体,至多只需要(130-π/180·cosα/2)2个探测仪器就可以重构出球内任意放置、任意形状的未知凸多面体。但是,在三维的情况下,以上的结论还有改进的空间,针对不同探测仪器个数带来的不同放置位置的特性,在最后一章节中,我们给出了4个以及6个探测仪器的最优放置情况下更好的上界。