This plugin will render Voronoi and Delaunay diagrams from a list of random points (sites). It uses Fortune’s algorithm (see libvoronoi.py) which is pretty fast; oddly enough, the slowest by far task in this plugin is the pdb.gimp_paintbrush_default part. Maybe I am doing something wrong…
Anyway, try a small number of sites first, and be sure to select a small brush (1 pixel is great) or the diagram will be a blob.
Extract the plugin to your ~/.gimpX.X/plug-ins folder under Linux or equivalent under Windows. The file py_tesselate.py must be executable.
You will find the plugin under Filters/Render/Tesselate