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

DOI10.1016/0020-0190(88)90165-2MaRDI QIDQ1111382zbMATH OpenOpenAlexFDO

Authors Frank Dehne, Ivan Stojmenović

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90165-2

zbMATH Keywords

computational geometryECDF searchingmesh-of-processorsparallel algorithm

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Review text

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\).

Recommendations

• Time lower bounds for sorting on multi-dimensional mesh-connected processor arrays
• d-dimensional range search on multicomputers
• A parallel algorithm for nearly optimal edge search
• Time lower bounds for parallel sorting on a mesh-connected processor array
• scientific article; zbMATH DE number 4035170
• A unified algorithm for sorting on multidimensional mesh-connected processors
• scientific article; zbMATH DE number 742956
• Indexing functions and time lower bounds for sorting on a mesh-connected computer
• Multisearch techniques: Parallel data structures on mesh-connected computers

Cites work

• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Maintenance of configurations in the plane
• Mesh computer algorithms for computational geometry
• Multidimensional divide-and-conquer
• On the equivalence of some rectangle problems
• Sorting on a mesh-connected parallel computer

Cited in

(1)

• Parallel general prefix computations with geometric, algebraic, and other applications

This page was built for publication: On O(\(\sqrt{n})\) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111382)