Parallel algorithms for spatial data

In this dissertation, we develop efficient parallel algorithms for spatial data problems. Our efficient solutions are based on a parallel computing strategy, which we call "pre-computing".; The Quadtree Medial Axis Transform (QMAT) representation of a binary image is a very useful scheme for computer graphics and image processing applications. QMAT representation is both compact and regular. We present an efficient algorithm for QMAT on the shared memory EREW-PRAM model. For an image of size {dollar}Ntimes N,{dollar} using {dollar}Ntimes N{dollar} processors, we compute QMAT in O(logN) time. Since image sensors provide image data as a two-dimensional array, the Mesh Connected Computer (MCC) is a popular architecture for image processing applications. Previously known parallel algorithm for QMAT require O(logN) time on a pyramid model, and a simulation of this algorithm will take O(NlogN) time on a MCC. However, our algorithm can be executed on a MCC in O(N) time, which is optimal for that model due to its diameter.; Boundary code or chain code is an efficient data structure for storage and transmission of image regions. However, for the purposes of manipulating an image a quadtree is more efficient. We develop efficient parallel (hypercube and EREW-PRAM) algorithms for building pointer-based and linear quadtrees from boundary/chain code image representation. For the input boundary code of length O(b) and the height O(h) of the output quadtree, our EREW-PRAM algorithm takes {dollar}O(h+logb){dollar} time, {dollar}O(b){dollar} processors and {dollar}O(bsp2){dollar} memory for quadtree building from boundary code. This improves upon a previously published CREW-PRAM algorithm requiring {dollar}O(h*logb){dollar} time, {dollar}O(b){dollar} processors and {dollar}O(b){dollar} memory. For the same task, our hypercube algorithm takes {dollar}O(h*logb){dollar} time and {dollar}O(b){dollar} processors, which also improves upon a previously published hypercube algorithm requiring {dollar}O(logb(h+logsp2logb)){dollar} time and {dollar}O(b){dollar} processors. Our work also implies an average case EREW-PRAM algorithm of the same time-processor complexity requiring only {dollar}O(b){dollar} memory. Our algorithms use a direct and simple 'sibling' finding technique for quadtrees; our technique exploits regularity in quadtree data structure, and it is applicable to any k-ary tree for which some (arbitrary) ordering exists among children nodes of a parent node.; The concept of R-tree, a hierarchical data structure, is a generalization of the concept of B-tree. A B-tree organizes a collection of "point" data, while R-trees provide a means of organizing a collection of geometric objects (of arbitrary shapes) by representing them as d-dimensional rectangles. Various operations on R-trees include addition, deletion and spatial queries. For n input objects (of arbitrary size) and a hypercube with at least n processors, our algorithm for R-tree building takes {dollar}O(logsp2N){dollar} time compared to {dollar}O(logsp3N){dollar} time taken by a previously published algorithm. Our parallel algorithm also implies a sequential algorithm with substantially improved worst-case time for R-tree building.