Random sampling techniques for efficient parallel algorithms in computational geometry

by Sen, Sandeep, Ph.D., Duke University, 1989, 134 pages; AAT 9025050

Abstract (Summary)

In this dissertation we investigate the use of random sampling techniques for obtaining parallel algorithms in computational geometry. One of the major thrust of research in parallel algorithms has been to minimize parallel time complexity without using a disproportionately large number of processors. In an ideal case the objective is to keep the total number of operations within a constant factor of the best known sequential time bounds for these problems. These algorithms are referred to as being 'optimal'. The model of computation used throughout is the PRAM model.

We have considered very fundamental problems including planar-point location, two variable linear programming, triangulation of simple polygon, convex hulls in two and three dimensions. In most cases we have been able to obtain O(log n) time algorithm using an optimal number of processors (except triangulation). Being very fundamental in nature, these problems imply equally efficient algorithms for various other problems including the 2-D Voronoi diagram of point sites. Presently no such deterministic algorithm is known for 3-D convex hulls or 2-D Voronoi diagrams. The randomized techniques often result in simple algorithms (compared to their deterministic counterparts) which is one of the main contributions of this thesis.

For developing the algorithms we have been able to make use of some known randomized techniques but for the parallel environment we require additional techniques. The more sophisticated algorithms rely on a new method called 'Polling' which seems to be a useful technique for a number of problems in computational geometry. Using this method one is able to obtain high-confidence bounds for algorithms as opposed to expected bounds. We also outline methods for limiting the number of purely random bits used by our algorithms while maintaining the claimed asymptotic bounds.

Indexing (document details)