SWEEP METHODS FOR PARALLEL COMPUTATIONAL GEOMETRY

In this paper we give efficient parallel algorithms for a number of pr oblems from computational geometry by using versions of parallel plane sweeping. We illustrate our approach with a number of applications, w hich include: General hidden-surface elimination (even if the overlap relation contains cycles). CSG boundary evaluation. Computing the cont our of a collection of rectangles. Hidden-surface elimination for rect angles. There are interesting subproblems that we solve as a part of e ach parallelization. For example, we give an optimal parallel method f or building a data structure for line-stabbing queries (which, inciden tally, improves the sequential complexity of this problem). Our algori thms are for the CREW PRAM, unless otherwise noted.