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 2007933697
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 give two optimal parallel algorithms for constructing the arrangement ofn lines in the plane. The first nethod is quite simple and runs inO(log2n) time usingO(n2) work, and the second method, which is more sophisticated, runs inO(logn) time usingO(n2) work. This second result solves a well-known open problem in parallel computational geometry, and involves the use of a new algorithmic technique, the construction of an ?-pseudocutting. Our results immediately imply that the arrangement ofn hyperplanes in ?d inO(logn) time usingO(nd) work, for fixedd, can be optimally constructed. Our algorithms are for the CREW PRAM.