# Fast Equipartition of Complex 2D Shapes with Minimal Boundaries +
## 2 Related Work
Clustering is an important problem in a broad spectrum of applications, such as data mining, computer vision, machine learning, and pattern recognition. Thousands of clustering algorithms have been proposed in the literature in many different scientific disciplines [23; 24] that differ in the choice of the objective function, probabilistic generative models, and heuristics. Clustering algorithms can be divided into two main categories: hierarchical and partitional:  
* Hierarchical clustering algorithms recursively find nested clusters in either an agglomerative (bottom-up) mode or in a divisive (top-down) mode. * According to partitional clustering algorithms, the clusters are simultaneously computed as a partition of the data. Usually, the partition is based on a local optimization of a given criterion. The \(K\)-means clustering algorithm [24; 25] is one of the simplest partitional clustering algorithms that solves the clustering problem for a given number of clusters. Even though \(K\)-means was first proposed over 50 years ago, it is still one of the most widely used algorithms for clustering. \(K\)-means is a centralized clustering algorithm with a linear computation cost. The goal of \(K\)-means is to minimize the sum of squared error (SSE) over all clusters, which is an NP-hard problem even for \(K=2\). \(K\)-means starts with \(K\) centroids, e.g., randomly selected in \(d\)-dimensional space, one for each candidate cluster. \(K\)-means converge to a local minimum of SSE. So, in the case where the given datasetsconsist of spherical and/or well-separated clusters, these centroids will eventually be placed at the centers of the clusters. In [26], a variant method (\(K\)-means++ algorithm) for centroid initialization has been proposed that chooses centers at random from the data points but weighs the data points according to their squared distance from the closest center already chosen. \(K\)-means++ usually outperforms \(K\)-means in terms of both accuracy and speed. An extension/variation of \(K\)-means is the \(K\)-medoid or Partitioning Around Medoids (PAM) [27], where the clusters are represented using the medoid of the data instead of the mean. Medoid is the object of the cluster with a minimum distance to all other objects in the cluster. Traditional clustering aims to minimize the mean square error without considering the balance of the cluster size. Balanced clustering is a two-objective optimization problem in which two objectives contradict each other: to minimize error and to balance cluster sizes [28]. In hard-balanced-constrained clustering, the cluster size balance is a mandatory requirement that must be met, and minimizing the Mean Square Error is a secondary criterion. Balance-constrained clustering can be solved in O(\(S^{3}\)), using a balanced k-means clustering algorithm that solves the assignment problem by the Hungarian algorithm [28], where \(S\) denotes the number of points. In soft-balanced clustering, balance is an aim but not a mandatory requirement. In [29], a soft-balanced clustering method based on the k-means clustering algorithm and network simplex methods has been proposed.