This paper studies the problem of enumerating all maximal collinear subsets of size at least three in a given set of @math points. An algorithm for this problem, besides solving degeneracy testing and the exact fitting problem, can also help with other problems, such as point line cover and general position subset selection. The classic algorithm of Edelsbrunner and Guibas can find these subsets in @math time in the dual plane. We present an alternative algorithm that, although asymptotically slower than their algorithm in the worst case, is simpler to implement and more amenable to parallelization. If the input points are decomposed into @math convex polygons, our algorithm has time complexity @math and space complexity @math . Our algorithm can be parallelized on the CREW PRAM with time complexity @math using @math processors.
Because topological sweeping is inherently sequential and thus unsuitable for parallel execution, parallel algorithms for sweeping or constructing arrangements have appeared in the literature. @cite_10 presented a CREW PRAM algorithm for constructing arrangements in @math time with @math processors and Goodrich @cite_17 presented an algorithm (also on the CREW PRAM) with the same goal with time complexity @math with @math processors. Since these algorithms construct the arrangement, they have space complexity @math , which is more than the @math space complexity of our parallel algorithm. Our algorithm also beats Goodrich's in time complexity, besides being easier to code since it uses only simple data structures.
@cite_10 @cite_17
2142561263 2022464277 1514117420 2121315472
We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log*n) time andn2 logn processors. We generalize this to obtain anO (logn log*n)-time algorithm usingnd logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement. We propose the jirst optimal parallel algorithm computing arrangements of hyperplanes in Ed (d 2 2). The algorithm is randomized and computes the arrangement of n hyperplanes within expected logarithmic time on a CRCW-PRAM with O(nd log n) processors. Topological sweep can contribute to efficient implementations of various algorithms for data analysis. Real data, however, has degeneracies. The modification of the topological sweep algorithm presented here handles degenerate cases such as parallel or multiply concurrent lines without requiring numerical perturbations to achieve general position. Our method maintains the O(n2) and O(n) time and space complexities of the original algorithm, and is robust and easy to implement. We present experimental results. 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.