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 planarpoint 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 2D Voronoi diagram of point sites. Presently no such deterministic algorithm is known for 3D convex hulls or 2D 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 highconfidence 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)
Advisor: 

School: 
Duke University 
School Location: 
United States  North Carolina 
Source: 
DAIB 51/04, p. 1929, Oct 1990 
Source type: 
Dissertation 
Subjects: 

Publication Number: 
AAT 9025050 



