An O(√n) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors
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.
|Keywords||ECDF searching, mesh-of-processors, parallel computational geometry|
|Journal||Information Processing Letters|
Dehne, F, & Stojmenovic, I. (Ivan). (1988). An O(√n) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors. Information Processing Letters, 28(2), 67–70. doi:10.1016/0020-0190(88)90165-2