Parallel geometric search on coarse-grained multicomputers

While still relatively young, computational geometry has rapidly grown Despite a grounding in applications, recently theory has significantly outstripped implementation, leaving a large gap between the two. As a result, emphasis is now being placed on the implementation and practical evaluation of algorithms and data structures with a focus on high performance computing platforms. This thesis presents two implementations of parallel segment trees—a fundamental data structure in computational geometry. Each emphasizes a different approach to the classical problem of the space-time tradeoff. In the first, memory use is optimized with a significant increase in computational complexity. In the second, observations regarding the structure of GIS data generated segment trees justifies a significantly simpler approach with noticeable performance improvements and in many cases near linear speedups.