Parallel algorithms for arrangements
Richard J Anderson, Paul W. Beame, Erik Brisson · 1990
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 of O(log n log * n) time and n²/log n processors. We generalize this to obtain an O(logn log* n) time algorithm using n^d/logn processors for solving the problem in d dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrange-ment of n lines on-line, in which each insertion is done in optimal O(logn) time using n / log n processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.