Parallel algorithms for some geometric problems based on a CREW PRAM /
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | Thesis Book |
| Language: | English |
| Published: |
1988.
|
| Subjects: | |
| Online Access: | ProQuest, Abstract Link to OAKTrust copy |
| Abstract: | The present dissertation centers on the design and construction of algorithms for some geometric problems using a CREW PRAM. A CREW PRAM is a parallel random access machine which allows different processors to address the same location simultaneously for reading but not for writing. In particular, the following geometric problems are to be addressed: (1) The maxima-finding (MAX) problem, (2) The empirical cumulative distribution function (ECDF) problem, (3) The isothetic rectangles intersection counting (RIC) problem, (4) The direct dominance reporting (DDR) problem, and (5) The vertical segment visibility reporting (SVR) problem. Given a set of N vectors in d dimensions, the MAX problem asks for the determination of the set of maximal elements (or maxima). The ECDF problem requires the computation of the rank of each element in the set. Given a set 5 of isothetic rectangles in d dimensions, the RIC problem calls for the computing for each rectangle R the number of rectangles in S that intersect R. An isothetic rectangle in d dimensions is the Cartesian product of d intervals, one on each of the d coordinate-axes and such that all edges of the rectangle are axis-parallel. The DDR problem demands that given a set 5 of points in the plane, for each element p in S, report all the other points in S that directly dominate p. Given a set of disjoint vertical segments in the plane, the SVR problem requests the determination of all the unique visibility pairs in the set. In this study, it was found that in d dimensions, where d > 1, the MAX problem, the ECDF problem, and the RIC problem all can be solved in O(log^[d-1]N) parallel time and O(N) space using O(N) processors on a CREW PRAM, where N denotes the input size. The DDR problem can be solved in time O(J+logN) and O(NlogN) space using O(N) processors, where J denotes the maximum of the number of direct dominances associated with any single point in the input set and N denotes the total number of input points. The planar SVR problem of size N can be solved in O(logN) time using O(A) space and O(N) processors on a CREW PRAM. |
|---|---|
| Item Description: | Typescript (photocopy). Vita. "Major subject: Computer Science." |
| Physical Description: | xi, 121 leaves : illustrations ; 29 cm |
| Bibliography: | Includes bibliographical references. |