Sweep methods for parallel computational geometry |
| |
Authors: | M T Goodrich M R Ghouse J Bright |
| |
Affiliation: | 1. Department of Computer Science, The Johns Hopkins University, 34th and Charles Street, 21218, Baltimore, MD, USA
|
| |
Abstract: | In this paper we give efficient parallel algorithms for a number of problems from computational geometry by using versions of parallel plane sweeping. We illustrate our approach with a number of applications, which include: General hidden-surface elimination (even if the overlap relation contains cycles). CSG boundary evaluation. Computing the contour of a collection of rectangles. Hidden-surface elimination for rectangles. There are interesting subproblems that we solve as a part of each parallelization. For example, we give an optimal parallel method for building a data structure for line-stabbing queries (which, incidentally, improves the sequential complexity of this problem). Our algorithms are for the CREW PRAM, unless otherwise noted. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|