## 1 Introduction  
Approximation of set-valued functions has various potential applications in optimization, mathematical economics, control, robotics and more. While approximation of set-valued functions with convex sets as images can be achieved with methods based on _Minkowski averages c.f._[1], it is shown in [2] that Minkowski averages are not suitable for approximation of set-valued functions with general (not necessarily convex) images. In order to develop approximation methods for set-valued functions with general images, other averaging operations on compact sets are required. Along with theoretical construction of such averaging operations, efficient algorithms for their computation are needed. First introduced by [PERSON] in [3], the _metric average_ of two compact sets in \(\mathbb{R}^{n}\) is a union of weighted averages between any point from any of the two sets and the subset of all its closest points from the other set. The interest in the metric average is due to its _metric property_ in relation to the Hausdorff distance [3]. The metric property of the metric average is that its Hausdorff distance from any of the averaged sets changes linearly with the weight parameter of the average. In [3], the metric average is used for piecewise linear approximation of set-valued functions. Extending these results, [PERSON] _et al._ applied the metric average to the approximation of set-valued functions from a finite number of their samples, using spline subdivision schemes and more generally positive approximation operators [4,5]. These methods are based on repeated computations of the metric average. The applicability of metric average based approximation methods requires efficient algorithms for the computation of the metric average of compact sets. An algorithm for the computation of the metric average of two 1D compact sets with computation time, which is linear in the number of connected subsets in the two sets, is introduced in [6]. A first step in the development of algorithms for the computation of the metric average of 2D sets is done in [7], where an algorithm for the computation of the metric average of two intersecting convex polygons is introduced and analyzed. The algorithm of [7] has linear time complexity in the number of vertices of the input polygons. In this work we introduce an algorithm that applies tools of computation geometry, segment Voronoi diagrams (_c.f._[8]) and planar arrangements (_c.f._[9]) to the computation of the metric average of 2D sets with piecewise linear boundaries. Such sets are collections of simple polygons and of simple polygons with holes. Since a compact 2D set with boundary consisting of closed curves can be linearly approximated by a 2D set with piecewise linear boundaries, our algorithm provides a computational method for approximation of set-valued functions with 2D images from a finite number of samples. Although the definition of the metric average of two sets with piecewise linear boundaries requires at least one operation for each point in the two sets, our algorithm reduces the computation to boundaries of cells of the partition of the two sets, obtained by the segment Voronoi diagram. The complexity of the algorithm is \(O\left(n^{2}\log n\right)\), where \(n\) is the total number of vertices on the boundaries of the two sets. Our algorithm is based on geometric objects such as segment Voronoi diagrams, arrangements of conic arcs and conic polygons with holes. We implemented the algorithm in C++, using the CGAL library [10], for handling the various geometric objects. The outline of this paper is as follows. Section 2 contains definitions and notation. In particular we review the main geometric concepts relevant to our work such as the metric average, segment Voronoi diagrams, planar arrangements and conic polygons with holes. In Section 3 we present the algorithm for the computation of the metric average of two simple polygons. The algorithm is extended to general 2D sets with piecewise linear boundaries in Section 4.