Based on this reddit discussion, I wanted to figure out what might be causing long narrow territories. Click on the polygons to toggle whether a territory starts there. I get long narrow territories when two points are close in one direction but there’s no nearby point in the perpendicular direction. I pre-populated the map with that effect on the top half, whereas the bottom half of the map has evenly spaced points. I use breadth first search expanding from all the seed points:
Also see the version on grids.