Method for Constructing Optimal Dark Coverings


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

The problem of constructing metric ε-nets and corresponding coverings by balls for compact sets with a probability measure is considered. In the case of sets having metrically significant parts with a small measure (dark sets), methods for constructing ε-nets are combined with the deep holes method in a unified approach. According to this approach, a constructed metric net is supplemented with its deep hole (the most distant element of the set) until the required accuracy is achieved. An existing implementation of the method for a metric set with a given probability measure is based on a pure global search for deep holes. To construct dark coverings, the method is implemented on the basis of a random multistart. For the resulting nets, the logarithm of the number of their elements is shown to be close to ε-entropy, which means that they are optimal. Techniques for estimating the reliability and completeness of constructed (ε, δ)-coverings in the sense of C.E. Shannon are described. The methods under consideration can be used to construct coverings of implicitly given sets with a measure defined on the preimage and to recover compact supports of multidimensional random variables with an unknown distribution law.

About the authors

G. K. Kamenev

Dorodnicyn Computing Center, Federal Research Center “Computer Science and Control”,
Russian Academy of Sciences

Author for correspondence.
Email: gkk@ccas.ru
Russian Federation, Moscow, 119333

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2018 Pleiades Publishing, Ltd.