В.Н. Ушаков, А.А. Ершов. Об оценке хаусдорфова расстояния между множеством и его выпуклой оболочкой в евклидовых пространствах малой размерности ... С. 223-235

УДК 517.977

MSC: 52A27, 52A30

DOI: 10.21538/0134-4889-2018-24-1-223-235

Полная версия статьи

Работа выполнена при поддержке РФФИ (проект 18-31-00018 мол_а).

В работе выводятся оценки хаусдорфова расстояния между множествами и их выпуклыми оболочками в конечномерных евклидовых пространствах со стандартным скалярным произведением и соответствующей нормой. В первой части работы данные оценки рассматриваются для $\alpha$-множеств. Под $\alpha$-множеством понимается произвольный компакт, у которого параметр, характеризующий степень невыпуклости и вычисляемый определенным образом, равен $\alpha$. В большинстве случаев упомянутый параметр $\alpha$ представляет собой максимальный возможный угол, под которым видны из точек, не принадлежащих рассматриваемому множеству, их проекции на это множество. $\alpha$-множества были введены В.Н. Ушаковым  для классификации невыпуклых множеств по степени их невыпуклости. Они используются для описания волновых фронтов и других задач, возникающих в теории управления. В работе рассмотрены $\alpha$-множества только в двумерном пространстве. Доказано, что если $\alpha$ мало, то соответствующие $\alpha$-множества близки к выпуклым множествам в хаусдорфовой метрике. Это позволяет пренебрегать их невыпуклостью и считать их выпуклыми, если известно, что параметр $\alpha$ мал. Отметим, что таким же образом часто применяется известная теорема Шепли - Фолкмана. Во второй части работы получены некоторое улучшение к оценке из самой теоремы Шепли - Фолкмана. В оригинальной теореме Шепли - Фолкмана утверждается, что сумма Минковского большого количества множеств близка в хаусдорфовой метрике к ее выпуклой оболочке по отношению к величине чебышёвского радиуса суммы. В данной работе рассмотрен частный случай, когда эта сумма состоит из одинаковых слагаемых, т. е. мы складываем некоторое множество $M$ само с собой. Для данного частного случая получено улучшение оценки, которое существенно для множеств в пространствах малой размерности. Кроме того, как и в известном следствии Старра, новая оценка допускает следующее улучшение: мы можем заменить чебышёвский радиус $R(M)$ в правой части оценки на внутренний радиус $r(M)$ множества $M$. Однако, отметим, что при неограниченном увеличении размерности пространства наша новая оценка асимптотически стремится к оценке, непосредственно вытекающей из теоремы Шепли - Фолкмана.

Ключевые слова: $\alpha$-множество, сумма Минковского, выпуклая оболочка, хаусдорфово расстояние.

СПИСОК ЛИТЕРАТУРЫ

1. Ушаков В.Н., Успенский А.А., Фомин А.Н. $\alpha$-множества и их свойства / Институт математики и механики УрО РАН. Екатеринбург, 2004. 62 c.

2. Ушаков В.Н., Успенский А.А. $\alpha$-множества в конечномерных евклидовых пространствах и их свойства // Вестн. Удмурт. ун-та. Математика. Механика. Компьют. науки. 2016. Т. 26, № 1. С. 95–120. doi: 10.20537/vm160109 .

3. Половинкин Е.С., Балашов М.В. Элементы выпуклого и сильно выпуклого анализа. М.: Физматлит, 2007. 438 с.

4. Яглом И.М., Болтянский В.Г. Выпуклые фигуры. М.: ГТТИ, 1951. 344 с.

5. Starr R.M. Quasi-equilibria in markets with non-convex preferences // Econometrica. 1969. Vol. 37, iss. 1. P. 25–38. doi: 10.2307/1909201 .

6. Гаркави А.Л. О чебышёвском центре и выпуклой оболочке множества // Успехи мат. наук. 1964. Т. 19, № 6. С. 139–145.

7. Бугров Я.С., Никольский С.М. Высшая математика: Учеб. для вузов: в 3 т. Т. 3: Дифференциальные уравнения. Кратные интегралы. Ряды. Функции комплексного переменного. М.: Дрофа, 2004. 512 с.

8. Препарата Ф., Феймос М. Вычислительная геометрия: Введение. М.: Мир, 1989. 478 с.

Поступила 10.09.2017

Ушаков Владимир Николаевич
чл.-корр. РАН, д-р физ.-мат. наук, профессор
главный науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН, г. Екатеринбург
e-mail: ushak@imm.uran.ru

Ершов Александр Анатольевич
канд. физ.-мат. наук
науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН, г. Екатеринбург
доцент
Челябинский государственный университет, г. Челябинск
e-mail: ale10919@yandex.ru

English

V.N. Ushakov, A.A. Ershov. An estimate of the Hausdorff distance between a set and its convex hull in Euclidean spaces of small dimension.

We derive estimates for the Hausdorff distance between sets and their convex hulls in finite-dimensional Euclidean spaces with the standard scalar product and the corresponding norm. In the first part of the paper, we consider estimates for $\alpha$-sets. By an $\alpha$-set we mean an arbitrary compact set for which the parameter characterizing the degree of nonconvexity and computed in a certain way equals $\alpha$. In most cases, the parameter $\alpha$ is the maximum possible angle under which the projections to this set are visible from points not belonging to the set. Note that $\alpha$-sets were introduced by V.N. Ushakov for the classification of nonconvex sets according to the degree of their nonconvexity; $\alpha$-sets are used for the description of wavefronts and for the solution of other problems in control theory. We consider $\alpha$-sets only in a two-dimensional space. It is proved that, if $\alpha$ is small, then the corresponding $\alpha$-sets are close to convex sets in the Hausdorff metric. This allows to neglect their nonconvexity and consider such sets convex if it is known that the parameter $\alpha$ is small. The known Shapley-Folkman theorem is often applied in the same way. In the second part of the paper we present some improvements of the estimates from the Shapley-Folkman theorem. The original Shapley-Folkman theorem states that the Minkowski sum of a large number of sets is close in the Hausdorff metric to the convex hull of this sum with respect to the value of the Chebyshev radius of the sum. We consider a particular case when the sum consists of identical terms; i.e., we add some set $M$ to itself. For this case we derive an improved estimate, which is essential for sets in spaces of small dimension. In addition, as in Starr's known corollary, the new estimate admits the following improvement: the Chebyshev radius $R(M)$ on the right-hand side can be replaced by the inner radius $r(M)$ of the set $M$. However, as the dimension of the space grows, the new estimate tends asymptotically to the estimate following immediately from the Shapley-Folkman theorem.

Keywords: $\alpha$-set, Minkowski sum, convex hull, Hausdorff distance.

The paper was received by the Editorial Office on September 10, 2017.

Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 18-31-00018 мол_а).

Vladimir Nikolaevich Ushakov, Dr. Phys.-Math. Sci., RAS Corresponding Member, Prof., Krasovskii
Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg,
620990 Russia, e-mail: ushak@imm.uran.ru .

Aleksandr Alekseevich Ershov, Cand. Sci. (Phys.-Math.), Krasovskii Institute of Mathematics and
Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia, Chelyabinsk
State University, Chelyabinsk, 454001 Russia, e-mail: ale10919@yandex.ru .