The big kludge was adding 8 points in adjacent squares. This isn't necessary. Instead calculate the x and y distances separately. If a distance is greater than .5, adjust it to 1 - distance. If a point is .7 from a v-point, it is .3 from a corresponding v-point in an adjacent square.

This means about 90% fewer v-points to test against, so this is many times faster.

So here's another version based on your changes with an additional color option.

YuckFoo

#!/usr/bin/perl

   use strict;
   use GD;

   my $ROWS   = 200;            # number of rows
   my $COLS   = 200;            # number of columns
   my $POINTS = 12;             # number of Voronoi points
   my $COLORS = 128;            # number of colors

   my $INNER = [255, 255,   0]; # inner color (red, green, blue)
   my $OUTER = [  0,  32,   0]; # outer color (red, green, blue)

   my $xfact = 1 / $COLS;
   my $yfact = 1 / $ROWS;

   # Allocate some colors
   my $img = new GD::Image($COLS, $ROWS);
   my $colors = makecolors($img, $COLORS, $INNER, $OUTER);

   my (@xs, @ys);

   # Pick some random points
   for (0..$POINTS-1) {
      push (@xs, rand());
      push (@ys, rand());
   }

   # Calculate screen
   for my $yi (0..$ROWS-1) {
      my $y = $yi * $yfact;
      for my $xi (0..$COLS-1) {
         my $x = $xi * $xfact;
         my ($best, $good) = closest($x, $y, \@xs, \@ys);

         $img->setPixel($xi, $yi, $colors->[$COLORS * ($best / $good)]
+);
      }
   }

   binmode STDOUT;
   print $img->png();
#-----------------------------------------------------------
sub closest {

   my ($x, $y, $xs, $ys) = @_;
   my ($dist, $best, $good);

   for (my $i = 0; $i < @$xs; $i++) {
      my $xdiff = abs($x - $xs->[$i]);
      my $ydiff = abs($y - $ys->[$i]);

      if ($xdiff > .5) { $xdiff = 1 - $xdiff; }
      if ($ydiff > .5) { $ydiff = 1 - $ydiff; }

      $dist = sqrt($xdiff * $xdiff + $ydiff * $ydiff);

      if    ($i == 0 || $dist < $best) { ($good, $best) = ($best, $dis
+t); }
      elsif ($i == 1 || $dist < $good) { $good = $dist; }
   }

   return ($best, $good);
}

#-----------------------------------------------------------
sub makecolors {

   my ($img, $num, $beg, $end) = @_;
   my (@colors);

   my $red   = ($end->[0] - $beg->[0]) / $num;
   my $green = ($end->[1] - $beg->[1]) / $num;
   my $blue  = ($end->[2] - $beg->[2]) / $num;

   for (my $i = 0; $i < $num; $i++) {
      $beg->[0] += $red;
      $beg->[1] += $green;
      $beg->[2] += $blue;
      push (@colors, $img->colorAllocate(@$beg));
   }

   return \@colors;
}
[download]