๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Optimal Parallel Algorithms for Quadtree Problems

โœ Scribed by S. Kasif

Publisher
Elsevier Science
Year
1994
Weight
449 KB
Volume
59
Category
Article
ISSN
1049-9660

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper we describe optimal processor-time parallel algorithms for set operations such as union, intersection, comparison on quadtrees. The algorithms presented in this paper run in (O(\log) (N) ) time using (N / \log N) processors on a shared memory model of computation that allows concurrent reads or writes. Consequently they allow us to achieve optimal speedups using any number of processors up to (N / \log N). The approach can also be used to derive optimal processor-time parallel algorithms for weaker models of parallel computation. 1994 Academic Press, Inc.

๐Ÿ“œ SIMILAR VOLUMES

Optimal Parallel Algorithms for Computer
Optimal Parallel Algorithms for Computer Vision Problems
โœ Chin-Hsiung Wu; Shi-Jinn Horng; Horng-Ren Tsai ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 315 KB

The computational model on which the algorithms are developed is the arrays with reconfigurable optical buses (abbreviated to AROB). It integrates the advantages of both optical transmission and electronic computation. In this paper, instead of using the radix-2 system, a radix-x system can be used

Parallel Algorithms for Orthotropic Prob
Parallel Algorithms for Orthotropic Problems
โœ Ivar Gustafsson; Gunhild Lindskog ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 784 KB

Finite element meshes and node-numberings suitable for parallel solution with equally loaded processors are presented for linear orthotropic elliptic partial differential equations. These problems are of great importance, for instance in the oil and airfoil industries. The linear systems of equation

Cyclic Interlaced Quadtree Algorithms fo
Cyclic Interlaced Quadtree Algorithms for Quincunx Multiresolution
โœ D.J. Hebert ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 317 KB

Recent advances in wavelet theory and in finite element computations draw attention to a well-known, simple, and computationally efficient triangulation method. We take a new look at this triangulation, which is obtained by repeated symmetric bisection, starting with a half square. The cells form th

Fast and Scalable Parallel Algorithms fo
Fast and Scalable Parallel Algorithms for Knapsack-like Problems
โœ Afonso Ferreira; John Michael Robson ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 403 KB

We present two new algorithms for searching in sorted X ุ‰ Y ุ‰ R ุ‰ S, one based on heaps and the other on sampling. Each of the algorithms runs in time O(n 2 log n) (n being the size of the sorted arrays X, Y, R, and S). Hence in each case, by constructing arrays of size n โ€ซุโ€ฌ O(2 s/4 ), we obtain a