Covering of High-Dimensional Cubes and Quantization
- PDF / 3,224,899 Bytes
- 32 Pages / 439.642 x 666.49 pts Page_size
- 45 Downloads / 141 Views
Covering of High-Dimensional Cubes and Quantization Anatoly Zhigljavsky1 · Jack Noonan1 Received: 24 February 2020 / Accepted: 14 May 2020 / © The Author(s) 2020
Abstract As the main problem, we consider covering of a d-dimensional cube by n balls with reasonably large d (10 or more) and reasonably small n, like n = 100 or n = 1000. We do not require the full coverage but only 90% or 95% coverage. We establish that efficient covering schemes have several important properties which are not seen in small dimensions and in asymptotical considerations, for very large n. One of these properties can be termed ‘do not try to cover the vertices’ as the vertices of the cube and their close neighbourhoods are very hard to cover and for large d there are far too many of them. We clearly demonstrate that, contrary to a common belief, placing balls at points which form a low-discrepancy sequence in the cube, results in a very inefficient covering scheme. For a family of random coverings, we are able to provide very accurate approximations to the coverage probability. We then extend our results to the problems of coverage of a cube by smaller cubes and quantization, the latter being also referred to as facility location. Along with theoretical considerations and derivation of approximations, we provide results of a large-scale numerical investigation. Keywords Covering · Quantization · Facility location · Space-filling · Computer experiments · High dimension Mathematics Subject Classification (2010) 90C26 · 65K99 · 65B99
Anatoly Zhigljavsky
[email protected] Jack Noonan [email protected] 1
School of Mathematics, Cardiff University, Cardiff, CF244AG, UK
18
Page 2 of 32
SN Operations Research Forum
(2020) 1:18
1 Introduction In this paper, we develop and study efficient schemes for covering and quantization in high-dimensional cubes. In particular, we will demonstrate that the proposed schemes are much superior to the so-called low-discrepancy sequences. The paper starts with introducing the main notation, then we formulate the main problem of covering a d-dimensional cube by n Euclidean balls. This is followed by a discussion on the main principles we have adopted for construction of our algorithms. Then we briefly formulate problems of covering a cube by smaller cubes (which are balls in the L∞ norm) and the problem of quantization. Both problems have many similarities with the main problem of covering a cube by n balls. At the end of this section, we describe the structure of the remaining sections of the paper and summarize our main findings. 1.1 Main Notation – – – – – –
– –
Rd : d-dimensional space; vectors in Rd are row-vectors; · and · ∞ : Euclidean and L∞ -norms in Rd ; Bd (Z, r) = {Y ∈ Rd : Y − Z ≤ r}: d-dimensional ball of radius r centred at Z ∈ Rd ; Bd (r) = Bd (0, r) = {Y ∈ Rd : Y ≤ r}; Sd (Z, r) = {Y ∈ Rd : Y − Z = r}: d-dimensional sphere of radius r centred at Z ∈ Rd ; Cd (Z, δ) = {Y ∈ Rd : Y − Z∞ ≤ δ}: d-dimensional cube of side length 2δ centred at Z (it is also the d-
Data Loading...
