Parallel algorithms for convex hulls and proximity problems
Amato, Nancy M.
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/21857
Description
Title
Parallel algorithms for convex hulls and proximity problems
Author(s)
Amato, Nancy M.
Issue Date
1995
Doctoral Committee Chair(s)
Preparata, Franco P.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
