2 I. Convex Sets at Large

provided

ζi = ξi + ηi for i = 1, . . . , d.

We can multiply a point by a real number:

if x = (ξ1, . . . , ξd) and α is a real number,

then

αx = (αξ1, . . . , αξd)

is a point from

Rd.

We consider the scalar product in

Rd:

x, y = ξ1η1 + . . . + ξdηd, where x = (ξ1, . . . , ξd) and y = (η1, . . . , ηd).

We define the (Euclidean) norm

x = ξ1 2 + . . . + ξd2

of a point x = (ξ1, . . . , ξd) and the distance between two points x and y:

dist(x, y) = x − y for x, y ∈

Rd.

Later in the text we will need volume. We do not define volume formally (that

would lead us too far away from the main direction of this book). Nevertheless,

we assume that the reader is familiar with elementary properties of the volume (cf.

Section 8.3). The volume of a set A ⊂ Rd is denoted vol A or vold A.

Let us introduce the central concept of the book.

(1.2) Convex sets, convex combinations and convex hulls.

Let {x1,... , xm} be a finite set of points from Rd. A point

x =

m

i=1

αixi, where

m

i=1

αi = 1 and αi ≥ 0 for i = 1, . . . , m

is called a convex combination of x1,... , xm. Given two distinct points x, y ∈ Rd,

the set

[x, y] = αx + (1 − α)y : 0 ≤ α ≤ 1

of all convex combinations of x and y is called the interval with endpoints x and

y. A set A ⊂

Rd

is called convex, provided [x, y] ⊂ A for any two x, y ∈ A, or in

words: a set is convex if and only if for every two points it contains the interval

that connects them. We agree that the empty set ∅ is convex. For A ⊂

Rd,

the

set of all convex combinations of points from A is called the convex hull of A and

denoted conv(A). We will see that conv(A) is the smallest convex set containing A

(Theorem 2.1).