Files in this item
Files  Description  Format 

application/pdf 9522076.pdf (5MB)  (no description provided) 
Description
Title:  Parallel algorithms for convex hulls and proximity problems 
Author(s):  Amato, Nancy M. 
Doctoral Committee Chair(s):  Preparata, Franco P. 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Computer Science 
Abstract:  Computational geometry is concerned with the algorithmic aspects of solving geometric problems. The problems are motivated from and have application to such diverse areas as computer graphics, robotics, computer vision, and operations research. Problems arising from these areas of application are good candidates for parallelization since they often have both intense computational needs and stringent response time requirements. Motivated by these concerns, this thesis investigates parallel algorithms for some basic geometric problems. The model of parallel computation used in our studies is the Parallel Random Access Machine (CREW PRAM). Constructing the convex hull of a set of n points in $\Re\sp3$ is one of the most studied problems in computational geometry. It is known that any parallel algorithm for this problem requires $\Omega(\log\ n)$ time, and must perform $\Omega(n \log\ n)$ work (i.e., the product of the time and the number of processors used by the algorithm). Despite the long held attention of many researchers, until recently no time or work optimal parallel algorithm was known for the threedimensional convex hull problem. We establish a criterion that can be used for constructing the merged hull of two disjoint subhulls, which forms the basis of an $O(\log\sp2 n)$ time and O(n) processor convex hull algorithm. Development of such a criterion had proven to be problematical in previous algorithms. Next, we show that the threedimensional convex hull problem can be solved in $O({1\over\alpha} \log\ n)$ time using $O(n\sp{1+\alpha}$) processors, for any constant 0 $< \alpha\ \le$ 1, by substituting manyway divideandconquer for the traditional twoway divideandconquer paradigm; this is the first timeoptimal parallel algorithm for this problem. Another important class of geometric problems is concerned with answering proximity queries about geometric objects. Let P and Q be simple polygons. Vertices $p \in P$ and $q \in Q$ are visible if $\overline {pq}$ does not properly intersect P or Q. The proximity problems considered in this thesis are: (i) finding a closest pair of boundary points between P and Q, and (ii) finding a closest pair of visible vertices between P and Q. For both problems, we give algorithms that run in $O(\log\ n)$ time (which is known to be optimal) using O(n) processors. For the first problem, the complexity of the best previous parallel algorithm was $O(\log\sp2 n)$ time using O(n) processors, and for the latter problem, no prior parallel algorithm was known. Serial versions of our parallel algorithms can be implemented in $\Theta(n)$ time. For problems of the first type, the complexity of the best previous sequential algorithm was $O(n \log n)$, and for problems of the second type, our sequential algorithm is simpler than all previous algorithms. 
Issue Date:  1995 
Type:  Text 
Language:  English 
URI:  http://hdl.handle.net/2142/21857 
Rights Information:  Copyright 1995 Amato, Nancy Marie 
Date Available in IDEALS:  20110507 
Identifier in Online Catalog:  AAI9522076 
OCLC Identifier:  (UMI)AAI9522076 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science