Computing faces in segment and simplex arrangements

For a set S of n line segments in the plane, we give the first work-optimal deterministic parallel algorithm for con-structing their arrangement. It runs in O(log2 n) time using O(n logn + k) work in the EREW PRAM model, where k is the number of intersecting line segment pairs, and pro-vides a fairly simple divide-and-conquer alternative to the optimal sequential “plane-sweep ” algorithm of Chazelle and Edelsbrunner. Moreover, our method can be used to out-put all k intersecting pairs while using only O(n) working space, which solves an open problem posed by Chazelle and Edelsbrunner. We also describe a sequential algorithm for computing a single face in an arrangement of n line seg-ments that runs in O(n2(n) logn) time, which improves on a previous O(n log2 n) time algorithm. For collections of simplices in IRd, we give methods for constructing a set ofm = O(nd1 logc n+k) cells of constant descriptive complexity that covers their arrangement, where c> 1 is a constant and k is the number of faces in the arrangement. The construction is performed sequentially in O(m) time, or in O(logn) time using O(m) work in the EREW PRAM model. The covering can be augmented to answer point location queries in O(logn) time. In addition to supplying the first parallel methods for these problems, we improve on the previous best sequential methods by reducing the query times (from O(log2 n) in IR3 and O(log3 n) in IRd, d> 3), and also the size and construction cost of the covering (from O(nd1+ + k)).