This book is concerned with the approximation of set-valued functions. It mainly presents our work on the design and analysis of approximation methods for functions mapping the points of a closed real interval to general compact sets in ℝn. Most previous results on approximation of set-valued functions were confined to the special case of functions with compact convex sets in ℝn as their values.
We present approximation methods together with bounds on the approximation error, measured in the Hausdorff metric. The error bounds are given in terms of the regularity of the approximated set-valued function.The regularity properties used are mainly of low order, such as Hölder continuity and bounded variation. This facilitates the analysis of approximation methods for non-smooth set-valued functions, which are common in areas such as optimization and control. The obtained error estimates are of similar quality to those for real-valued functions.
Our work was motivated by the need to approximate a set-valued function from a finite number of its samples. Such a need arises in the problem of "reconstruction" of a 3D object from its parallel cross-sections, which are compact 2D sets, and also in the numerical solution of non-linear differential inclusions. In the latter problem the set-valued solution has to be approximated from a discrete collection of its computed values, which are not necessarily convex sets.
The approach taken in this book is to adapt classical linear approximation operators for real-valued functions to set-valued functions. For sample-based operators, the main method of adaptation is to replace operations between numbers by operations between sets. The main difficulty in this approach is the design of set operations, which yield operators with approximation properties. A second method is based on representations of set-valued functions by collections of real-valued functions. Having such a representation at hand, the approximation of the set-valued function is reduced to the approximation of the corresponding collection of representing real-valued functions. The main effort in this approach is the design of an appropriate representation consisting of real-valued functions with regularity properties "inherited" from those of the approximated setvalued function.
The book consists of three parts. The first presents basic notions and results needed to establish the adapted approximation methods, and to carry out their analysis. The second part is concerned with several approximation methods for set-valued functions with compact sets in ℝn as their values. The third part is devoted to the simpler case n = 1, where special representations of such set-valued functions are designed, and approximation methods based on these representations are discussed.
The subject of the book is on the border of the two fields Set-Valued Analysis and Approximation Theory. The panoramic view, given in the book can attract researchers from both fields to this intriguing subject. In addition, the book will be useful for researchers working in related fields such as control and game theory, mathematical economics, optimization and geometric modeling.
The bibliography covers various related topics. To improve the readability of the book, references to the bibliography do not appear in the text, but are deferred to special sections, mostly at the end of chapters.
We would like to thank the School of Mathematical Sciences at Tel-Aviv University for giving us a supporting and stimulating environment for carrying out our research, and for presenting it in this book.

Preface v

Notations x

I Scientific Background 1

1. On Functions with Values in Metric Spaces 3

      1.1 Basic Notions 3

      1.2 Basic Approximation Methods 6

      1.3 Classical Approximation Operators 7

      1.3.1 Positive operators 8

      1.3.2 Interpolation operators 12

      1.3.3 Spline subdivision schemes 13

      1.4 Bibliographical Notes 15

2. On Sets 17

      2.1 Sets and Operations Between Sets 17

      2.1.1 Definitions and notation 17

      2.1.2 Minkowski linear combination 18

      2.1.3 Metric average 19

      2.1.4 Metric linear combination 21

      2.2 Parametrizations of Sets 23

      2.2.1 Induced metrics and operations 23

      2.2.2 Convex sets by support functions 24

      2.2.3 Parametrization of sets in ℝ 25

      2.2.4 Star-shaped sets by radial functions 27

      2.2.5 General sets by signed distance functions 28

      2.3 Bibliographical Notes 29

3. On Set-Valued Functions (SVFs) 31

      3.1 Definitions and Examples 31

      3.2 Representations of SVFs 32

      3.3 Regularity Based on Representations 35

      3.4 Bibliographical Notes 37

II Approximation of SVFs with Images in ℝn 39

4. Methods Based on Canonical Representations 41

      4.1 Induced Operators 41

      4.2 Approximation Results 43

      4.3 Application to SVFs with Convex Images 45

      4.4 Examples and Conclusions 48

      4.5 Bibliographical Notes 51

5. Methods Based on Minkowski Convex Combinations 53

      5.1 Spline Subdivision Schemes for Convex Sets 54

      5.2 Non-Convexity Measures of a Compact Set 57

      5.3 Convexification of Sequences of Sample-Based Positive Operators 59

      5.4 Convexification by Spline Subdivision Schemes 61

      5.5 Bibliographical Notes 63

6. Methods Based on the Metric Average 65

      6.1 Schoenberg Spline Operators 66

      6.2 Spline Subdivision Schemes 71

      6.3 Bernstein Polynomial Operators 76

      6.4 Bibliographical Notes 82

7. Methods Based on Metric Linear Combinations 85

      7.1 Metric Piecewise Linear lnterpolation 86

      7.2 Error Analysis 91

      7.3 Multifunctions with Convex Images 94

      7.4 Specific Metric Operators 95

      7.4.1 Metric Bernstein operators 95

      7.4.2 Metric Schoenberg operators 96

      7.4.3 Metric polynomial interpolation 97

      7.5 Bibliographical Notes 99

8. Methods Based on Metric Selections 101

      8.1 Metric Selections 101

      8.2 Approximation Results 104

      8.3 Bibliographical Notes 106

III Approximation of SVFs with Images in ℝ 107

9. SVFs with Images in ℝ 109

      9.1 Preliminaries on the Graphs of SVFs 110

      9.2 Continuity of the Boundaries of a CBV Multifunction 112

      9.3 Regularity Properties of the Boundaries 116

10. Multi-Segmental and Topological Representations 121

      10.1 Multi-Segmental Representations (MSRs) 121

      10.2 Topological MSRs 126

      10.2.1 Existence of a topological MSR 127

      10.2.2 Conditions for uniqueness of a TMSR 130

      10.3 Representation by Topological Selections 134

      10.4 Regularity of SVFs Based on MSRs 135

11. Methods Based on Topological Representation 137

      11.1 Positive Linear Operators Based on TMSRs 137

      11.1.1 Bernstein polynomial operators 139

      11.1.2 Schoenberg operators 141

      11.2 General Operators Based on Topological Selections 142

      11.3 Bibliographical Notes to Part III 144

Bibliography 145

Index 151

中科院文献情报中心