An Adaptive, Parallel Algorithm for Approximating the Generalized Voronoi Diagram

A Generalized Voronoi Diagram (GVD) partitions a space into regions based on the distance between arbitrarily-shaped objects. Each region contains exactly one object, and consists of all points closer to that object than any other. GVDs have applications in pathfinding, medical analysis, and simulation. Computing the GVD for many datasets is computationally intensive. Standard techniques rely on uniform gridding of the space, causing failure when the number of voxels becomes prohibitively large. Other techniques use adaptive space subdivision which avoid failure at the expense of efficiency. Unlike previous approaches, we are able to break up the construction of GVDs into novel work items. We then solve these items in parallel on graphics cards, improving performance. Using these techniques, GVD construction becomes much more efficient, practical, and applicable