- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Geometric hierarchies and parallel subdivision search
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Geometric hierarchies and parallel subdivision search Dadoun, Nounou Norman
Abstract
Geometric hierarchies have proven useful for the problems of point location in planar subdivisions and 2- and 3-dimensional convex polytope separation on a sequential model of computation. In this thesis, we formulate a geometric hierarchy paradigm (following the work of Dobkin and Kirkpatrick) and apply this paradigm to solve a number of computational geometry problems on a shared memory (PRAM) parallel model of computation. For certain problems, we describe what we call cooperative algorithms, algorithms which exploit parallelism in searching geometric hierarchies to solve their respective problems. For convex polygons, the geometric hierarchies are implicit and can be exploited in cooperative algorithms to compute convex polygon separation and to construct convex polygon separating/common tangents. The paradigm is also applied to the problem of tree contraction which is, in turn, applied to a number of specialized point location applications including the parallel construction of 2-dimensional Voronoi Diagrams. For point location in planar subdivisions, we present parallel algorithms to construct a subdivision hierarchy representation. A related convex polyhedra hierarchy is constructed similarly and applied to the parallel construction of 3-dimensional convex hulls. The geometric hierarchy paradigm is applied further to the design of a data structure which supports cooperative point location in general planar subdivisions. Again, a related polyhedral hierarchy can be used to exploit parallelism for a cooperative separation algorithm for convex polyhedra.
Item Metadata
Title |
Geometric hierarchies and parallel subdivision search
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
1990
|
Description |
Geometric hierarchies have proven useful for the problems of point location in planar subdivisions and 2- and 3-dimensional convex polytope separation on a sequential model of computation. In this thesis, we formulate a geometric hierarchy paradigm (following the work of Dobkin and Kirkpatrick) and apply this paradigm to solve a number of computational geometry problems on a shared memory (PRAM) parallel model of computation. For certain problems, we describe what we call cooperative algorithms, algorithms which exploit parallelism in searching geometric hierarchies to solve their respective problems.
For convex polygons, the geometric hierarchies are implicit and can be exploited in cooperative algorithms to compute convex polygon separation and to construct convex polygon separating/common tangents. The paradigm is also applied to the problem of tree contraction which is, in turn, applied to a number of specialized point location applications including the parallel construction of 2-dimensional Voronoi Diagrams.
For point location in planar subdivisions, we present parallel algorithms to construct a subdivision hierarchy representation. A related convex polyhedra hierarchy is constructed similarly and applied to the parallel construction of 3-dimensional convex hulls. The geometric hierarchy paradigm is applied further to the design of a data structure which supports cooperative point location in general planar subdivisions. Again, a related polyhedral hierarchy can be used to exploit parallelism for a cooperative separation algorithm for convex polyhedra.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2011-01-31
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
|
DOI |
10.14288/1.0052039
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.