On O(\(\sqrt{n})\) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors (Q1111382)

The first author [ibid. 22, 303-306 (1986)] presented an optimal O(\(\sqrt{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\geq 4.\) We solve this problem by presenting an optimal O(\(\sqrt{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(\(\sqrt{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\geq 4\).