# Fast Equipartition of Complex 2D Shapes with Minimal Boundaries +
## Appendix A  
In this appendix, we study the relationship between the (8-pixel connectivity) graph-based distance \(GD_{8}(.)\), the Euclidean distance and the complete graph-based distance \(GD(.)\), as defined in Section 5, and we propose an approximation of the graph-based distance of a complete graph that combines the Euclidean distance, and \(GD_{8}(.)\). Figure 11a shows examples of graph-based distances \(GD_{8}(.)\) and \(GD(.)\) between the point \(p_{1}\) and some points (\(p_{2}\), \(p_{3}\) and \(p_{4}\)) of the image space using gray and blue lines, respectively. In this example, for any pair of points, it holds that the complete graph-based distance \(GD(.)\) is equal to the corresponding Euclidean distance. Concerning the \(GD_{8}(.)\), it is equal to the corresponding Euclidean distances (or \(GD(.)\)) for pixels \(p_{2}\in S\) with angle \(\measuredangle p_{1}p_{2}\in\{0^{\circ},45^{\circ},90^{\circ},135^{\circ},180^{ \circ},225^{\circ},270^{\circ},315^{\circ}\}\) (see the white pixels in Figure 11a).  
\[GD_{8}(p_{1},p_{2})=GD(p_{1},p_{2})\Leftrightarrow\measuredangle p_{1}p_{2}=k \cdot\frac{\pi}{4},\{k\in\mathbb{N}\} \tag{1}\]  
In Figure 11a, it holds that  
\[GD_{8}(p_{1},p_{2})=|p_{1}-p_{5}|_{2}+|p_{2}-p_{5}|_{2}=\frac{\sqrt{2}+1}{ \sqrt{5}}|p_{1}-p_{2}|_{2}\]  
\[GD_{8}(p_{1},p_{3})=|p_{1}-p_{6}|_{2}+|p_{3}-p_{6}|_{2}=\frac{\sqrt{2}+1}{ \sqrt{5}}|p_{1}-p_{3}|_{2}\]  
\[GD_{8}(p_{1},p_{4})=|p_{1}-p_{7}|_{2}+|p_{4}-p_{7}|_{2}=\frac{\sqrt{8}+1}{ \sqrt{13}}|p_{1}-p_{4}|_{2}\]  
Due to the 8-pixel connectivity of the graph \(G\), it holds that \(GD_{8}(p_{1},p_{2})\geq GD(p_{1},p_{2})\geq|p_{1}-p_{2}|_{2}\). More specifically, it holds that the ratio \(\frac{GD_{8}(p_{1},p_{2})}{GD(p_{1},p_{2})}\leq\frac{\sqrt{2}+1}{\sqrt{5}}\). This ratio is maximized for the pixels \(p_{2}\in S\) with angle \(\measuredangle p_{1}p_{2}=\frac{\pi}{8}+k\cdot\frac{\pi}{4}\), \(\{k\in\mathbb{N}\}\) (see the orange-colored pixels of Figure 11a). This direction corresponds to the bisector of the directions where the two distances are identical according to the Equation (1). Therefore, it holds that  
\[\frac{\sqrt{5}}{\sqrt{2}+1}\cdot GD_{8}(p_{1},p_{2})\leq GD(p_{1},p_{2})\leq GD _{8}(p_{1},p_{2}) \tag{2}\]  
The graph-based distance \(GD(p_{1},p_{2})\) of a complete graph of shape \(S\) between two points \(p_{1}\in S\) and \(p_{2}\in S\) is equal to the Euclidean distance \(|p_{1}-p_{2}|_{2}\) if and only if thepoints of the line segment \(p_{1}p_{2}\) belong to the shape \(S\). Otherwise, it holds that \(GD(p_{1},p_{2})>|p_{1}-p_{2}|_{2}\). Moreover, it holds that \(GD(p_{1},p_{2})\leq GD_{8}(p_{1},p_{2})\). These distances are equal if and only if the shortest paths between the points \(p_{1}\), \(p_{2}\) under two graphs are identical. Examples of such cases are shown in Figure 14. Therefore, taking also into account the Inequality (A2), it holds that the graph-based distance \(GD(p_{1},p_{2})\) can be approximated by the \(GD_{8}(p_{1},p_{2})\) and the \(|p_{1}-p_{2}|_{2}\) as follows:  
\[\widehat{GD}(p_{1},p_{2})=max(\frac{\sqrt{5}}{\sqrt{2}+1}GD_{8}(p_{1},p_{2}),| p_{1}-p_{2}|_{2}).\] (A3)