Non-lattice Covering and Quantization of High Dimensional Sets

The main problem considered in this paper is construction and theoretical study of efficient n-point coverings of a d-dimensional cube [−1, 1]^d. Targeted values of d are between 5 and 50; n can be in hundreds or thousands and the designs (collections of points) are nested. This paper is a continuation of our paper (Noonan and Zhigljavsky, SN Oper Res Forum, 2020), where we have theoretically investigated several simple schemes and numerically studied many more. In this paper, we extend the theoretical constructions of (Noonan and Zhigljavsky, SN Oper Res Forum, 2020) for studying the designs that were found to be superior to the ones theoretically investigated in (Noonan and Zhigljavsky, SN Oper Res Forum, 2020). We also extend our constructions for new construction schemes that provide even better coverings (in the class of nested designs) than the ones numerically found in (Noonan and Zhigljavsky, SN Oper Res Forum, 2020). In view of a close connection of the problem of quantization to the problem of covering, we extend our theoretical approximations and practical recommendations to the problem of construction of efficient quantization designs in a cube [−1, 1]^d. In the last section, we discuss the problems of covering and quantization in a d-dimensional simplex; practical significance of this problem has been communicated to the authors by Professor Michael Vrahatis, a co-editor of the present volume.