## 6 Complexity Bounds
Note that under the conditions of Lemma 6.4, \(p_{1}\in\partial A\) and \(p_{2}\in\partial B\), and therefore we get, in view of Corollary 6.2, that  
**Corollary 6.5**: The sets \(A\bigcap B,M_{t}\left(A\backslash B,\partial B\right),M_{1-t}\left(B\backslash A,\partial A\right)\) have pairwise disjoint interiors. Next we discuss the combinatorial complexity of the metric average of two simple polygons. The discussion is based on the notion of the combinatorial complexity of a planar arrangement, which is the sum of the number of vertices, the number of edges, and the number of faces in the arrangement. **Proposition 6.6**: Let \(n\) be the sum of the numbers of vertices in \(A\) and in \(B\). The combinatorial complexity of \(A\oplus_{t}B\) with \(t\in\left[0,1\right]\) is \(O\left(n^{2}\right)\). _Proof._ The combinatorial complexity of \(A\bigcap B\) is \(O\left(n^{2}\right)\) and the combinatorial complexity of \(VD_{\partial B}\) is \(O\left(n\right)\)[8]. Since the metric faces in \(MF_{\partial B}\left(A\backslash B\right)\) are partial to the overlay of the arrangements representing \(VD_{\partial B},\partial A\) and \(\partial B\) their total combinatorial complexity is \(O\left(n^{2}\right)\) and the same bound holds for the metric faces in \(MF_{\partial A}\left(B\backslash A\right)\). By Corollaries 6.3 and 6.5, (6.1) is a union of sets with pairwise disjoint interiors. So the combinatorial complexity of \(A\oplus_{t}B\) is bounded by the combinatorial complexity of \(A\bigcap B\) and the combinatorial complexity of the metric faces, namely it is \(O\left(n^{2}\right)\). Finally we derive the run-time complexity of our algorithm. **Proposition 6.7**: Let \(n\) be the sum of the numbers of vertices in \(A\) and in \(B\). Let \(k\) be the combinatorial complexity of the overlay of the arrangements representing \(\partial A,\partial B,VD_{\partial A}\) and \(VD_{\partial B}\). Then the run-time complexity of the computation of the metric average \(A\oplus_{t}B\) is \(O\left((n+k)\log n\right)\). _Proof._ It follows from the proof of Proposition 6.6 that \(k\) is \(O\left(n^{2}\right)\). Computation of the sets \(A\bigcap B\), \(A\setminus B\), \(B\setminus A\) can be done in \(O\left(n+k\right)\log n\) and the combinatorial complexity of each of these sets is bounded by \(k\)[15]. The segment Voronoi diagrams \(VD_{\partial A}\) and \(VD_{\partial B}\) can be computed in \(O\left(n\log n\right)\)[8]. Since the metric faces in \(MF_{\partial B}\left(A\backslash B\right)\) are computed by the overlay of the arrangements representing \(A\backslash B\) and \(VD_{\partial B}\), with the combinatorial complexity of the result bounded by \(k\), they can be found in \(O\left(n+k\right)\log n\). Computation of \(M_{t}\left(\partial F,S\left(F\right)\right)\) for all metric faces in \(MF_{\partial B}\left(A\backslash B\right)\) is performed in \(O\left(k\right)\). The same bounds hold for metric faces in \(MF_{\partial A}\left(B\backslash A\right)\). Finally we compute \(A\oplus_{t}B\) as in (6.1). By the proof of Proposition 6.6 the combinatorial  
Voronoi diagrams and planar arrangements. The implementation of the algorithm uses the relevant geometric algorithms in the CGAL [10] library. The main idea of our algorithm, namely the simplification of the computation of the metric average with Voronoi diagrams has straightforward extension to any two objects in any finite dimension, such that the Voronoi diagrams of the boundaries of the two objects are well defined. A natural extension of this work is to develop and implement an algorithm for the computation of the metric average of two polyhedra. Whereas the metric average is of interest in applications where the Hausdorff distance is important, it does not possess good geometric properties, as is indicated by the examples in Section 5. For geometric applications, it is of interest to develop set averaging operations that possess good geometric properties, i.e.