CONSTRUCTING ARRANGEMENTS OPTIMALLY IN PARALLEL

We give two optimal parallel algorithms for constructing the arrangeme nt of n lines in the plane. The first method is quite simple and runs in O(log2 n) time using O(n2) work, and the second method, which is mo re sophisticated, runs in O(log n) time using O(n2) work. This second result solves a well-known open problem in parallel computational geom etry, and involves the use of a new algorithmic technique, the constru ction of an epsilon-pseudocutting. Our results immediately imply that the arrangement of n hyperplanes in R(d) in O(log n) time using O(n(d) ) work, for fixed d, can be optimally constructed. Our algorithms are for the CREW PRAM.