high performance computing on graphics processing units: hgpu.org

Polygon overlay is one of the complex operations in computational geometry. It is applied in many fields such as Geographic Information Systems (GIS), computer graphics, VLSI CAD, etc. We have two significant results to report. Our first result is the first output-sensitive CREW PRAM algorithm for simple polygons, which can perform typical set operations including intersection, union, and difference in O(logn) time using (n+k) processors, where n is the number of vertices and k is the number of edge intersections. The current best algorithm by Karinthi, Srinivas, and Almasi [1] does not handle self-intersecting polygons, is not output-sensitive and must employ Theta(n^2) processors to achieve O(logn) time. Our algorithm is superior to [1] in all three aspects. Spatial data files tend to be large in size (in GBs) and the underlying overlay computation is highly irregular and compute intensive. Our second result is a GIS system, namely MPI-GIS, for end-to-end polygonal overlay processing over heterogeneous clusters. It employs R-tree for efficient indexing and identification of potentially intersecting set of polygons across two input GIS layers. MPI-GIS can leverage multi-cores and many-cores using a combination of MPI and CUDA to accelerate polygon overlay. This system achieves 44X speedup on a 32-node IBM iDataPlex cluster while processing about 600K polygons in two GIS layers within 19 seconds.