## 6 Complexity Bounds  
In this section we discuss the run-time complexity bounds for our algorithm and the combinatorial complexity of the obtained set. We assume here that \(A,B\) are simple polygons, and the extension of the results of this section to 2D sets with piecewise linear boundaries is straightforward. The complexity bounds depend on the well known complexity of the underlying algorithms for the computation of segment Voronoi diagrams and planar arrangements. Recall that by (2.4) and (3.4),  
\[A\oplus_{t}B=A\bigcap B\bigcup_{F\in MF_{\partial B}(A\setminus B)}M_{t}\left( F,S\left(F\right)\right)\bigcup_{F\in MF_{\partial A}(B\setminus A)}M_{1-t} \left(F,S\left(F\right)\right). \tag{6.1}\]  
Our main task in this complexity analysis is to show that (6.1) is a union of simple conic polygons with pairwise disjoint interiors. For this goal, we first prove several results about the metric average that will be later used in the complexity analysis. **Lemma 6.1**: Let \(p_{1},p_{2}\in\mathbb{R}^{2}\setminus B\) such that \(p_{1}\
eq p_{2}\), then for \(t\in(0,1)\)  
\[M_{t}\left(p_{1},\partial B\right)\bigcap M_{t}\left(p_{2},\partial B\right)=\phi.\]  
_Proof._ Assume to the contrary that there exists a point \(p\) in \(M_{t}\left(p_{1},\partial B\right)\bigcap M_{t}\left(p_{2},\partial B\right)\), then there exist \(s_{i}\in\Pi_{\partial B}\left(p_{i}\right),i=1,2\) such that  
\[p=tp_{1}+\left(1-t\right)s_{1}=tp_{2}+\left(1-t\right)s_{2}. \tag{6.2}\]From above equality we conclude that \(s_{1}\
eq s_{2}\). Without loss of generality assume, that  
\[\left|p-s_{2}\right|\leq\left|p-s_{1}\right|. \tag{6.3}\]  
Recall, by definition, that  
\[\left|p_{1}-s_{2}\right|\geq\left|p_{1}-s_{1}\right|. \tag{6.4}\]  
Since \(p_{1}\
eq p_{2}\) and \(s_{1}\
eq s_{2}\), (6.2) implies \(\left[p_{1},s_{1}\right]\bigcap\left[p_{2},s_{2}\right]=p\). Thus by (6.3), \(\left|p_{1}-s_{2}\right|<\left|p_{1}-s_{1}\right|\) in contradiction to (6.4). An immediate consequence of Lemma 6.1 is  
**Corollary 6.2**: Let \(p\in M_{t}\left(A\backslash B,\partial B\right)\), then there is a unique point \(q\in A\setminus B\), denoted by \(q=G(p)\), such that \(p\in M_{t}\left(q,\partial B\right)\). Moreover simple geometric arguments imply that for \(p_{1},p_{2}\in M_{t}\left(A\backslash B,\partial B\right)\), \(\left|G\left(p_{1}\right)-G\left(p_{2}\right)\right|\leq\frac{1}{t}\left|p_{1 }-p_{2}\right|.\)  
Since any two metric faces contained in the same polygon have disjoint interiors, we conclude from the above lemma,  
**Corollary 6.3**: Let \(F_{1},F_{2}\) be metric faces such that \(F_{1},F_{2}\subset A\), then \(M_{t}\left(F_{1},S\left(F_{1}\right)\right)\) and \(M_{t}\left(F_{2},S\left(F_{2}\right)\right)\) have disjoint interiors. Next we prove a result complementing Lemma 6.1. **Lemma 6.4**: Let \(p_{1}\in A\setminus B\), \(p_{2}\in B\setminus A\). If  
\[M_{t}\left(p_{1},\partial B\right)\bigcap M_{1-t}\left(p_{2},\partial A\right) \
eq\phi,\]  
then  
\[p_{1}\in\Pi_{\partial A}\left(p_{2}\right)\;\mathrm{and}\;p_{2}\in\Pi_{ \partial\mathrm{B}}\left(p_{1}\right).\]  
_Proof._ Let \(p\in M_{t}\left(p_{1},\partial B\right)\bigcap M_{t}\left(p_{2},\partial A\right)\), then there exist points \(s_{1}\in\Pi_{\partial B}\left(p_{1}\right)\) and \(s_{2}\in\Pi_{\partial A}\left(p_{2}\right)\) such that  
\[p=tp_{1}+\left(1-t\right)s_{1}=\left(1-t\right)p_{2}+ts_{2}. \tag{6.5}\]  
Without loss of generality assume that  
\[\left|p_{2}-s_{2}\right|\leq\left|p_{1}-s_{1}\right|. \tag{6.6}\]  
By definition,  
\[\left|p_{1}-s_{1}\right|\leq\left|p_{1}-p_{2}\right|. \tag{6.7}\]  
By (6.5) and (6.6),  
\[M_{t}\left(p_{1},\partial B\right)\bigcap M_{t}\left(p_{2},\partial B\right)=\phi.\]0  
We prove the lemma by contradiction. Suppose \(p_{1}\
eq s_{2}\), then by (6.5) \(p_{2}\
eq s_{1}\). Thus \(\left[p_{1},s_{1}\right]\bigcap\left[p_{2},s_{2}\right]=p\), and therefore by (6.8) \(\left|p_{1}-p_{2}\right|<\left|p_{1}-s_{1}\right|\), which is a contradiction to (6.7).