Previous page: Publications - Papers of the Project


Robert Baier, Elza Farkhi

Directed Sets and Differences of Convex Compact Sets

The paper is published in:
Michael P. Polis, Asen L. Dontchev, Peter Kall, Irena Lasiecka, Andrzej W. Olbrot (eds.): Systems Modelling and Optimization, Proceedings of the 18th IFIP TC7 Conference 1997, Pitman Research Notes in Mathematics Series, 396. Chapman and Hall/CRC, 1999, pp. 135-143.
MSC:
52A01 Axiomatic and generalized convexity
52A20 Convex sets in $n$ dimensions (including convex hypersurfaces), See also {53A07, 53C45}
52A30 Variants of convex sets (star-shaped, ($m, n$)-convex, etc.)
65D05 Interpolation
26E25 Set-valued functions, See also {28B20, 54C60}, {For nonsmooth analysis, See 49J52, 58Cxx, 90Cxx}
28B20 Set-valued set functions and measures; integration of set-valued functions; measurable selections, See Also {26E25, 54C60, 54C65, 90A14}
65G10 Interval and finite arithmetic
46B20 Geometry and structure of normed linear spaces
06B30 Topological lattices, order topologies, See also {06F30, 22A26, 54F05, 54H12}

Keywords:
difference of convex, compact sets; embedding of convex, compact sets in a vector space;
visualization of differences of sets;

Abstract:
A linear normed and partially ordered space is introduced,
in which the convex cone of all nonempty convex compact sets
in Rn is embedded. This space of
so-called "directed sets" is a Banach and a Riesz space for
dimension n > 2 and a Banach lattice for
n = 1.

We use essentially the specific parametrization of convex
compact sets via their support functions and consider the
supporting faces as lower dimensional convex sets.
Extending this approach, we define a directed set as a pair
of a scalar function and a mapping that associates to each
unit direction a (n-1)-dimensional directed set
("supporting" part). This approach enables us to construct
all definitions and operations recursively and to prove
everything inductively.

The definition of a directed set could be distinguished
from other existing embeddings (equivalence classes in
[H. Rådström: An embedding theorem for spaces of convex
sets, 1952] and [K. E. Schmidt: Embedding Theorems for
Classes of Convex Sets, 1986] resp. real-valued functions
on Rn in [P. L. Hörmander: Sur la
fonction d'appui des ensembles convexes dans un espace
localement convexe, 1954]) by the fact that a visualization
as sets in Rn with attached
directions is possible for directed sets, e.g. differences
of embedded convex sets. The parametrization with outer
normals and the use of "supporting" faces and functions
ensures a convenient computer realization.

The approach is based on the notions of generalized
([E. Kaucher: Über Eigenschaften und Anwendungsmöglichkeiten
der erweiterten Intervallrechnung und des hyperbolischen
Fastkörpers über R, 1977], [E. Kaucher: Interval
Analysis in the Extended Interval Space IR, 1980],
[H.-J. Ortolf: Eine Verallgemeinerung der
Intervallarithmetik, 1969]) or directed intervals
([S. Markov: On the presentation of ranges of monotone
functions using interval arithmetics, 1992], [S. Markov: On
directed interval arithmetic and its applications, 1995])
in the one-dimensional case. In the n-dimensional
case, there are essential differences, namely a mixed type
part appears which does not exist in the case n=1.

One should also mention the interesting
computational-geometrical approach of polygonal tracings
in ([L. Guibas, L. Ramshaw, J. Stolfi: A kinematic
framework for computational geometry, 1983]) and the notion
of convolution of tracings exploiting paths and tangents.

As an application we give an example of set-valued
interpolation where nonconvex visualizations of directed
sets appear as results.

Table of Contents:
1. Introduction
2. Directed Intervals
3. Directed Sets
4. Applications and Numerical Examples


© Robert Baier
Last modified: Wed May 27 10:41:50 MDT 1998