## 3 The Algorithm for Simple Polygons  
Here we assume that \(A,B\) are simple polygons. We begin with the representation (2.4) of the metric average. The main part of the computation of the metric average is the computation of the sets \(M_{t}\left(A\setminus B,\partial B\right)\) and \(M_{1-t}\left(B\setminus A,\partial B\right)\) with \(0<t<1\). We describe in details the computation of \(M_{t}\left(A\setminus B,\partial B\right)\). First we apply a sequence of reductions, which simplify the computations. The main idea is to partition \(A\setminus B\) by the segment Voronoi diagram induced by \(\partial B\). We show that it is sufficient to perform the computations only on the boundary curves of the cells of this partition. Denote by \(VD_{\partial B}\) the collection of faces of the segment Voronoi diagram induced by the \(\partial B\). The Voronoi faces in \(VD_{\partial B}\) constitute a partition of the plane. Therefore the set \(A\setminus B\) can be represented as,  
\[A\setminus B=\bigcup_{F\in VD_{\partial B}}((A\setminus B)\bigcap F), \tag{3.1}\]  
and thus, by the definition of \(M_{t}\) in (2.1),  
\[M_{t}\left(A\setminus B,\partial B\right)=\bigcup_{F\in VD_{\partial B}}M_{t} \left((A\setminus B)\bigcap F,\partial B\right). \tag{3.2}\]  
Denoting by \(S\left(F\right)\) the Voronoi site associated with a Voronoi face \(F\), we observe that by the definition of \(VD_{\partial B}\), the closest point on \(\partial B\) to \(p\in F\in VD_{\partial B}\) is on \(S\left(F\right)\), and obtain  
\[M_{t}\left(A\setminus B,\partial B\right)=\bigcup_{F\in VD_{\partial B}}M_{t} \left((A\setminus B)\bigcap F,S(F)\right). \tag{3.3}\]We call a connected component of \(F\bigcap(A\setminus B)\) with non-empty interior a _metric face_ of \(F\). For \(\tilde{F}\) a metric face of \(F\), we define \(S(\tilde{F})=S(F)\). We denote by \(MF_{\partial B}(A\setminus B)\) the collection of all the metric faces induced by the Voronoi faces in \(VD_{\partial B}\) and by \(A\setminus B\). With this notation (3.3) can be rewritten as,  
\[M_{t}\left(A\setminus B,\partial B\right)=\bigcup_{F\in MF_{\partial B}(A \setminus B)}M_{t}\left(F,S(F)\right). \tag{3.4}\]  
In order to compute \(M_{t}\left(A\setminus B,\partial B\right)\) using the reduction (3.4), it is required first to find the metric faces and then for each metric face \(F\) to compute \(M_{t}\left(F,S\left(F\right)\right)\),  
The computation of the metric faces are based on planar arrangements. The bisectors of the segment Voronoi diagram are conic curves [8], hence \(VD_{\partial B}\) constitutes an arrangement of conic segments. Obviously \(A\backslash B\) can be represented by an arrangement of linear segments. Thus the metric faces are the intersections of the bounded faces of the two arrangements and can be computed by the overlay of these two arrangements. Next we show that the computation of \(M_{t}\left(F,S\left(F\right)\right)\) for a metric face \(F\) can be further reduced to the computation of \(M_{t}\left(\partial F,S\left(F\right)\right)\). The Voronoi site \(S(F)\) is either an open linear segment or a point, thus the set \(\Pi_{S(F)}(p)\) of all projection points of a point \(p\in\mathbb{R}^{2}\) on \(S(F)\) is a singleton. It is easy to see, that the operation \(p\to M_{t}\left(p,S\left(F\right)\right)\), can be regarded as a continuous one-to-one function from the metric face \(F\) to \(\mathbb{R}^{2}\). Consequently, \(M_{t}\left(\partial F,S\left(F\right)\right)\) is a simple closed curve, since the boundary of a metric face is so. Thus the region bounded by \(M_{t}\left(\partial F,S\left(F\right)\right)\) is \(M_{t}\left(F,S\left(F\right)\right)\), and it is sufficient to compute \(M_{t}\left(\partial F,S\left(F\right)\right)\).