On a Few Progressive Algorithms

Abstract

The progressive algorithms are algorithms that outputs intermediate solutions which approximate the complete solution to the given problem. The user can decide whether to continue the running of the algorithm based on the error of the partial solutions. In this dissertation, we have studied few problems from the perspective of progressive algorithm. We have proposed the following: Hu man encoding: a progressive algorithm for nding optimal pre x encoding or hu man coding. We have proved that error of the partial solution in step r is bounded by n=2r􀀀2. Overall running time of the algorithm, we have shown, is O(n log n). Convex hull in 2D: Next, we have moved towards geometric problems. We have presented a randomized progressive algorithm for nding convex hull of the points in R2. The algorithm runs in at most log n many rounds and expected running time of each round is O(n). Convex hull in 3D: We have also extended an existing progressive algorithm for nding convex hull of the points in R2 for the point set in R3. We have proposed a procedure to have an upper bound of O(log n) for the number of rounds of the algorithm for this problem. This work uses one observation whose proof eludes us but we have compelling experimental evidence for the observation.