Dynamic Programming Acceleration Algorithm And Contour Detection Algorithm

In this thesis, we studied the dynamic programming speedups and camera probe problems in both2d and3d cases.Many problems including image processing, network routing, speech recogni-tion and others in the area of mathematics, computer science and computational biology can be expressed as recurrences. Thus we can use dynamic programming to solve these problems. And what’s more, when the dynamic programming satis-fy some properties, we can speedup the time of the algorithms. And surprisingly, many problems satisfy convexity and concavity.In the first part of our paper, we discuss how to speed up the calculation of a generic Dynamic Program (DP) in the form where Dr is dependent upon C[1], C[2],..., C[r-1], Li is some non-decreasing weight function, and g(x) is a given "failure" function.This general DP models many problems in multiple domains and has there-fore been extensively studied. In particular, calculating C[n] should a-priori require O(n2) time but, if g(x) is concave, convex or some combination of con-vex/concave pieces, various authors have shown that the time can be dramatically reduced down to "almost" linear and, in some special cases, completely linear. The "almost" is a term involving the inverse Ackermann function which is a very slowly growing function.However in the first part of the thesis we will introduce a new geometric technique that, in many cases, gets rid of the inverse Ackermann function. Our algorithm transforms the dynamic programming into the geometric problem of maintaining a lower envelope. In this case, we can obtain purely linear time calculation of C[n]. And compare to the previous algorithms, our algorithm is much simpler and easy to understand (especially compare to these convex al-gorithms). We also extend our algorithms to the case that g(x) is piecewise convex/concave with k pieces. Through dividing the problem into several sub-problems and maintaining k lower envelops, we could solve the problem in O(nk) time while the previous best algorithm by Eppstein needs O(nka(n/k)) time and also with the constraint that Li=i.In the second part of the thesis, we will introduce a new problem in the geometric probing area, which is called camera probe. Assume there is an un-known polygon inside of a disk of radius1, the camera probe problem is to find the minimum number of cameras at fixed positions necessary and sufficient to reconstruct any such polygons.The model we proposed is based on an "863" project. One of the problem we need to solve is to fix several cameras to reconstruct certain convex polygons. Actually Geometric Probing is the area that focus on these kind of researches. In1987, Cole and Yap first introduced Geometric Probing into computational geometry with their new model named finger probe. Since then, a set of different geometric probings including finger probe, hyperplane probe, silhouette probe., were being extensively studied. However, all these models require the probing machine is fixed and the next probing direction should depend on the previous probing results. In our new model, we could fixed all the cameras before. Besides, different from other geometric probing problems that the optimal probe number always depends on the number of vertices of the polygon, while in our camera probe problem, the number of cameras only depends on the the largest a of the polygon.In general positions in two-dimension, if no two camera tangents overlap,[3π/π-α] cameras are necessary and sufficient. Otherwise, we show that approx-imately [4π/π-α] cameras are sufficient to reconstruct any polygons with largest angle a. Besides, we will present a linear time algorithm to reconstruct the unknown polygon.In three-dimension case, there’s an unknown convex polyhedron inside a ball of radius1, and all cameras are on the sphere of the ball. The number of cameras needed depends on the largest face-to-face angle of the polyhedron. Based on the features of the vertices that can be seen by the cameras, we transform the problem into the problem of finding the placement of certain number of cameras so that the distance between each point on the sphere to the nearest camera is minimized. Thus we eet the result that for anv polvhedron with largest face-to-face angle α, we need at most (130-π/180·cosα/2)2cameras.However, the result in3d case is not optimal. When the placement of the cameras satisfy some special properties, e.g. symmetric to the center of the ball, we can obtain better bound. In the last chapter, we gave better upper bounds of a for4,6camera placements.