Achanta and Süsstrunk, based on their earlier work on SLIC , propose SNIC – Simple Non-Iterative Clustering – for improved superpixel segmentation. Their approach is comparably simple and also closely related to other superpixel algorithms such as SEEDS . In particular, instead of running $k$-means in a local neighborhood (of fixed size) around a superpixel center, superpixels are grwon from initial centroids. The initialization is the same as SLIC, then a queue of pixels is created by visting the neighbors of the centroids, and their neighbors and so on. The queue makes sure to visit the pixels in an order based on their similarity to the centroid. Each time, a pixel is added to a superpixel, the corresponding centroid is updated. As similarity measure, they follow SLIC and use a distance based on color and location. This growing of initial centroids in illustrated in Figure 1.
Figure 1: Illustration of how the initial centroids evolve. Green indicates the start point, white the points taken while updating and red the final point.
Above considering superpixels as application, they also propose a new “polygon segmentation” method, i.e. an algorithm segmenting an image into polygons. This task was first approached in  where an image is decomposed into convex polygons. The proposed method, called SNICPOLY, does not necessarily produce convex polygons though. Figure 2 shows an example illustrating the process of deriving polygons from superpixels.
In experiments, they show that SNIC outperforms SLIC in terms of the F-measure. Personally, however, I do not find this measure meaningful to evaluate superpixels as it includes Boundary Precision. However, as the goal is to produce an oversegmentation, Boundary Precision is not meaningful. Regarding Undersegmentation Error, SNIC and SLIC perform roughly equally well. Finally, SNIC is slightly faster than SLIC, however, still scales similarly with increasing image sizes. I refer to the paper for experimental results.