An O(√n) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors

Abstract

Dehne (1986) presented an optimal O(√n) 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 d≥4. In this paper we solve this problem by presenting an optimal O(√n) time parallel solution to the d-dimensional ECDF searching problem for arbitrary dimension d = O(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(√n) for arbitrary dimension d = O(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 d≥4. © 1988.