Files in this item



application/pdf9522076.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF


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 Urbana-Champaign
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 three-dimensional 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 three-dimensional 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 many-way divide-and-conquer for the traditional two-way divide-and-conquer paradigm; this is the first time-optimal 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
Rights Information:Copyright 1995 Amato, Nancy Marie
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9522076
OCLC Identifier:(UMI)AAI9522076

This item appears in the following Collection(s)

Item Statistics