O(LOG LOG N)-TIME INTEGER GEOMETRY ON THE CRCW PRAM

We study problems in computational geometry on PRAMs under the assumpt ion that input objects are specified by points with O(log n)-bit coord inates, or, equivalently, with polynomially bounded integer coordinate s. We show that in this setting many geometric problems can be solved in time O(log log n). The following five specific problems are investi gated: CLOSEST PAIR OF POINTS, INTERSECTION OF CONVEX POLYGONS, INTERS ECTION OF MANHATTAN LINE SEGMENTS, DOMINATING SET, and LARGEST EMPTY S QUARE. Algorithms solving them are developed which operate in time O(l og log n) on the arbitrary CRCW PRAM. The number of processors used is either O(n) or O(n log n).