# Fast Equipartition of Complex 2D Shapes with Minimal Boundaries +
## 1 Introduction  
Image segmentation is a fundamental problem in the fields of computer vision and pattern recognition and plays a crucial role in a wide range of applications. These applications span various domains, including object recognition [1], remote sensing [2], and medical image analysis [3]. At its core, image segmentation involves the division of an image into meaningful regions or segments, facilitating higher-level analysis and interpretation. The task can be formulated in two principal ways: as a classification problem at the pixel level, known as semantic segmentation, or as an object-specific partitioning problem, referred to as instance segmentation. The curve equipartition problem has been formally defined, explored, and solved in [4]. This problem has numerous applications across various domains, including polygonal approximation, signal modeling, and video summarization. The objective of the curve equipartition problem is to identify \(N-1\) consecutive points along a given curve such that the curve is divided into \(N\) segments of equal chord lengths under a predefined distancefunction (see Figures 1 and 2). This partitioning ensures that each segment maintains a consistent measure in terms of the chord length, which makes it highly relevant in geometric and computational applications. In [4], a level set approach is adopted to establish that for any continuous injective curve in a metric space and for any given number \(N\), there always exists at least one valid \(N\)-equipartition. Furthermore, an approximate algorithm inspired by the level set approach is proposed to efficiently compute all possible solutions with high accuracy. The number of solutions to this problem generally depends on both the shape of the curve and the chosen value of \(N\). In particular, for certain special classes of curves, the number of solutions for some values of \(N\) may be infinite. A geometric proof, provided in [4], demonstrates that the curve equipartition problem always has at least one solution for every continuous injective curve, regardless of the number of partitions. Figure 2 illustrates the two distinct solutions for the curve equipartition problem with \(N=5\). In this figure, the computed partition points (depicted in green) are projected onto the curve \(c(t)\) (represented by the blue curve) and are connected by red line segments. An interesting extension of the curve equipartition problem involves generalizing its formulation and solution techniques to different mathematical and computational structures, including meshes [5], images [6], and shapes [7]. These extensions open up new avenues for research and practical applications in geometric processing, computer vision, and pattern recognition. In our previous work [7], a general version of the 2D shape equipartition problem (2D-SEP) with minimum intrinsic boundary length has been presented. According to the 2D shape equipartition problem, the goal is to compute a shape segmentation into \(N\) equal-area segments so that the length (\(L\)) of the intrinsic boundary between the segments is minimized. We have shown that for any convex shape \(S\), the 2D-SEP problem has at least one solution for any value of \(N\), even if the intrinsic boundaries are line segments. However, when a non-convex 2D shape is given, there exist some cases where the 2D-SEP has no solution even for \(N=2\). In [7], two methods have been proposed to solve 2D-SEP:  
* A region-growing-based method that solves the general version of 2D-SEP problem called _SEP-RG_;  
Figure 1: A curve equipartition example for \(N=3\), \(|AP_{1}|=|P_{1}P_{2}|=|P_{2}B|\). Figure 2: Two solutions with different chord lengths of curve equipartition problem with \(N=5\) are projected on the curve \(c(t)\) (blue curve) with the green color points connected with red line segments. * A sequential selection method that efficiently solves the problem under the constraint that the intrinsic boundaries are line segments called _SEP-ILS_.