Recent PhD Theses - 1

Author	Neelima Gupta
Title	Efficient Parallel Output-Size Sensitive Algorithms
Thesis Supervisor	Sandeep Sen
Date of Defence	November, 1998
Institute granting Degree	Indian Institute of Technology, Delhi
Current Address

Abstract

We present efficient PRAM algorithms whose performance is related to the size of the output of the given instance (of a problem). For a number of geometric problems, the output-size is often smaller than the worst-case behavior in terms of the input-size. With careful design, output-sensitive algorithms exhibit superior performance for these problems than the worst-case optimal algorithms. We address the following problems in this report: Convex hulls in two and three dimensions, Vector maxima in two and three dimensions and Hidden surface elimination problem for terrains.

Most of our algorithms improve the previously best-known results known for these problems in terms of running time, and/or work-bound. Some of our algorithms exploit randomized techniques to provide faster solutions. For convex hulls in two dimensions our algorithms are faster for small output sizes than the previously known output sensitive algorithms keeping the work optimal. In three dimensions our algorithm is faster for all output sizes. We obtain similar results for vector-maxima in two and three dimensions. To the best of our knowledge, no previous parallel output-sensitive algorithm was known for 3-D vector maxima. We also present sublogarithmic-time optimal algorithms that use superlinear number of processors for vector maxima in two and three dimensions. For the hidden surface elimination problem for terrains, our algorithm is simpler than the previous work and is more complete in its description of the details.

Further, we present some distribution sensitive algorithms for planar hulls, vector maxima and multiset sorting problems which provide superior solutions than the previous output-sensitive algorithms. The notion of distribution is defined in the context of each of the problems.

Next Thesis