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=2r2. 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.