Covering of high-dimensional sets

Abstract: Let

(m a t h c a l X, h o)

be a metric space and

l a m b d a

be a Borel measure on this space defined on the

s i g m a

-algebra generated by open subsets of

m a t h c a l X

; this measure

l a m b d a

defines volumes of Borel subsets of

m a t h c a l X

. The principal case is where

m a t h c a l X = m a t h b b R^{d}

,

h o

is the Euclidean metric, and

l a m b d a

is the Lebesgue measure. In this article, we are not going to pay much attention to the case of small dimensions

d

as the problem of construction of good covering schemes for small

d

can be attacked by the brute-force optimization algorithms. On the contrary, for medium or large dimensions (say,

d g e q 10

), there is little chance of getting anything sensible without understanding the main issues related to construction of efficient covering designs.

This page was built for publication: Covering of high-dimensional sets