If all you need is an image of colored Voronoi regions (and no actual graph structures), there are faster algorithms, for example based on http://fab.cba.mit.ed

If all you need is an image of colored Voronoi regions (and no actual graph structures), there are faster algorithms, for example based on http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance... which run in O(width * height + number_of_points) instead of O(width * height + number_of_points * number_of_pixels_on_cone) as this GPU implementation does.