computation of the metric average of 2d sets with piecewise linear boundaries计算度量平均的2 d组与分段线性边界.pdfVIP

Algorithms 2010, 3, 265-275; doi:10.3390/a3030265 OPEN ACCESS algorithms ISSN 1999-4893 /journal/algorithms Article Computation of the Metric Average of 2D Sets with Piecewise Linear Boundaries Shay Kels , Nira Dyn and Evgeny Lipovetsky School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv, Israel; E-Mail: niradyn@tau.ac.il PTC Corp, Parametric Tech. Israel Ltd., Herzliya, Israel; E-Mail: elipovetsky@ Author to whom correspondence should be addressed; E-Mail: kelsisha@tau.ac.il; Tel.: +972-50-9950465. Received: 5 May 2010; in revised form: 8 July 2010 / Accepted: 22 July 2010 / Published: 26 July 2010 Abstract: The metric average is a binary operation between sets in which is used in the approximation of set-valued functions. We introduce an algorithm that applies tools of computational geometry to the computation of the metric average of 2D sets with piecewise linear boundaries. Keywords: metric average; computational geometry; computational complexity; Voronoi diagrams; 2D arrangements 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