Narrow Results

The log cost measure has been viewed as a more reasonable method of measuring the time complexity of an algorithm than the unit cost measure. The more widely used unit cost measure becomes unrealistic if the algorithm handles extremely large integers. Parallel machines have not been examined under the log cost measure. In this paper, we investigate the Parallel Random Access Machine under the log cost measure. Let the instruction set of a basic PRAM include addition, subtraction, and Boolean operations. We relate resource-bounded complexity classes of log cost PRAMs to complexity classes of Turing machines and circuits. We also relate log cost PRAMs with different instruction sets by simulations that are much more efficient than possible in the unit cost case. Let LCRCW^k(CRCW^k) denote the class of languages accepted by a log cost (unit cost) basic CRCW PRAM in O(log^k n) time with the polynomial in n number of processors. We position the log cost PRAM in the hierarchy of parallel complexity classes as: AC^k=CRCW^k⊆(NC^k+1, LCRCW^k+1)⊆AC^k+1=CRCW^k+1.

In this paper we prove the correctness of a “local” criterion for computing the convex hull of the union ( “merging”) of two disjoint convex polyhedra. This criterion is structural. Therefore it can be algorithmically tested in several ways, not necessarily involving the determination of support (tangent) planes; indeed, it can be implemented by just testing for the intersection of certain planes and lines with convex polytopes. This criterion is amenable to parallel implementation and leads to a provably correct algorithm that computes the convex hull of any n points in three-dimensional space in O(log² n) time using O(n) processors on a CREW PRAM.