TR-121: n O(√n) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors

Abstract

[1] presented an optimal O(‘Jn} time parallel algorithm for solving the ECDF searching problem for a set of n points in two- and three-dimensional space on a Mesh-of­Processors of size n. However, it remained an open problem whether such an optimal solution exists for the d-dimensional ECDF searching problem for d4.
In this paper we solve this problem by presenting an optimal O(“-Jri} time parallel solution to the d-dimensional ECDF searching problem for arbitrary dimension d= 0(1} on a Mesh-of-Processors of size n.
The algorithm has several interesting implications. Among others the following problems can now be solved on a Mesh-of-Processors in (asymptotically optimal} time O(‘Jn} for arbitrary dimension d=0(1}: the d-dimensional maximal element determination problem, the d-dimensional hypercube containment counting problem, and the d-dimensional hypercube intersection counting problem. The latter two problems can be mapped to the 2d-dimensional ECDF searching problem but require an efficient solution to this problem for at least d4.