# Fast Equipartition of Complex 2D Shapes with Minimal Boundaries +
## 1 Introduction
The experimental results demonstrated that _SEP-RG_ outperformed _SEP-ILS_[7]. In this work, we study in more depth the 2D shape equipartition problem (2D-SEP), studying optimal solutions for basic geometric shapes. Additionally, we propose two methods for solving 2D-SEP:
* A 2D Shape Equipartition algorithm based on a fast balanced clustering method (SEP-FBC);
* A Particle Swarm Optimization (PSO) method that uses the SEP-FBC method, called _SEP-PSO FBC_. _SEP-FBC_ uses initial seeds as _SEP-RG_, but instead of successive executions of region-growing steps of _SEP-RG_, firstly, it performs hard clustering and then performs a growing-shrinking process that gradually improves satisfaction with the criterion of equal-area regions. This results in a low computation cost method that makes possible its integration with Particle Swarm Optimization (PSO) framework, resulting on the top-performing method _SEP-PSO FBC_. To our knowledge, SEP-FBC is the most computationally efficient method to solve 2D-SEP. According to our experimental in about 90% of 25,758 segmentation instances, the proposed methods clearly outperform in terms of intrinsic boundary length the current methods from the literature (_SEP-RG_ and _SEP-ILS_). On average, the intrinsic boundary length of the SEP-PSO FBC is 7.2% lower compared to the corresponding intrinsic boundary length of the top-performing method _SEP-RG_ from the literature. Figure 3 presents examples of the proposed 2D-SEP for different numbers of segments (\(N\in\{2,3,4,5\}\)). In the first and second rows, the results come from the _SEP-ILS_ and _SEP-RG_ methods [7], respectively. In the third row, the corresponding results come from the proposed _SEP-FBC_ method. In any case, the segmentation consists of \(N\) equal-area segments. However, the intrinsic boundary length (\(L\)) differs by method. Figure 3a shows a segmentation of an apple for \(N=2\), where a solution of a line segment close to the diameter of the apple seems to be the optimal solution of 2D-SEP. In this simple example, as expected, the _SEP-ILS_ method, which exclusively uses line segments, yields the lowest intrinsic boundary length \(L=46.1\). Figure 3i shows a corresponding segmentation using the proposed _SEP-FBC_ method that yields a slightly higher intrinsic boundary length \(L=46.4\). In more complex examples (see Figure 3i-l), the proposed _SEP-FBC_ method yields a lower intrinsic boundary length than the other methods. In summary, the main contributions of our work are the following:  
* To the best of our knowledge, this is the first work that extensively studies the 2D-SEP problem under the minimum intrinsic boundary length. * We study for the first time basic problem instances, providing the optimal 2D-SEP problem solutions of partitioning of a square and circle into two, three, four, and five equal-area regions and analyzing the case of partitioning of a plane into a high number of equal-area regions. * We study for the first time the properties of 2D-SEP, including the total intrinsic boundaries' length of the optimal 2D-SEP solution as a sequence of N.
* We propose a fast balanced clustering method (SEP-FBC) that can be combined with a Particle Swarm Optimization (PSO) framework, due to its lower computational cost compared to the baselines from the literature, to efficiently solve the general version of the 2D-SEP problem. * The quantitative results obtained on more than 2800 2D shapes included in two standard datasets quantify the outer performance of the proposed methods from baselines of the literature. The rest of this paper is organized as follows: Section 2 reviews the related work for image segmentation and balanced clustering algorithms. The 2D-SEP problem formulation is given in Section 3. In Section 4, 2D-SEP instances and properties are studied. Section 5 presents the two proposed methods for solving 2D-SEP, respectively. Section 6 describes the experimental setup along with the results obtained. Finally, conclusions and future work are provided in Section 7.