Аппроксимация вполне ограниченных множеств методом глубоких ям

Предлагается метод глубоких ям (МГЯ) – универсальный адаптивный итерационный метод аппроксимации вполне ограниченных множеств в произвольных метрических пространствах на основе построения близких к оптимальным метрических $\varepsilon$-сетей и $\varepsilon$-различимых подмножеств (построения эффективных покрытий и упаковок шаров). Показано, что при заданной мощности метрической $\varepsilon$-сети МГЯ позволяет строить аппроксимацию с радиусом покрывающих шаров, не более чем вдвое большим минимально возможного. Рассмотрен пример реализации МГЯ для покрытия конечного множества, содержащего $N$ элементов, $n$ метрическими шарами. Показано, что за время, не превышающее $O(nN)$, МГЯ позволяет строить $\varepsilon$-покрытие, для которого число шаров $n$ не больше максимального числа точек $\varepsilon$-различимого подмножества аппроксимируемого множества. Рассмотрена реализация МГЯ для аппроксимации неявно заданных множеств и при аппроксимации гладких выпуклых тел многогранниками.