А.3. Метрика Хаусдорфа II

Мы продолжим обсуждение расстояния Хаусдорфа между двумя множествами в начатое в п. 3.5. Через К. обозначим совокупность всех непустых компактных подмножеств Несмотря на то, что в качестве основной метрики на мы принимаем евклидову метрику, определения и теоремы настоящего раздела применимы и к произвольной полной метрике, включая и -метрики на Иначе говоря, каждой полной метрике соответствует некоторая метрика Хаусдорфа на К.. Упражнения содержат примеры использования так называемой манхэттенской метрики.

Рис. А.1.

Определим расстояние между точкой и множеством следующим образом (рис. А.1):

Предостережение: расстояние здесь и далее в этом приложении не должно автоматически интерпретироваться как метрика в соответствии с определением из п. 3.2. Некоторые расстояния, которые мы рассмотрим, не удовлетворяют аксиомам метрики.

Строго говоря, следует использовать вместо в определении . Однако, так как множество Е предполагается компактным, то фактически означает то же самое, что и (упр. 5 в конце параграфа).

Обобщим понятие расстояния от точки до компактного множества Е. Определим расстояние между двумя компактными множествами Е и F следующим образом (рис. А.2):

Рис. А.2.

Строго говоря, следует использовать вместо но вследствие того, что оба множества компактны, корректно и использование Более того, всегда существуют такие точки что (упр. 6 в конце параграфа).

Естественно задать вопрос: является ли расстояние метрикой? Очевидно, нет. В частности, если , причем , то (упр. 8 в конце параграфа), что нарушает одно из свойств метрики.

Так что же, поиск метрики для К. обречен на неудачу? К счастью, нет. Фактически, мы остановились слишком рано. Нам потребуется еще несколько новых понятий. Для вещественных чисел а и b введем:

Рис. А.3. Метрика Хаусдорфа Н(Е, F)

Определение метрики Хаусдорфа на К. таково (рис. А.3):

Мы докажем, что Н(Е, F) является метрикой, в несколько этапов. Некоторые из них оставлены в качестве упражнений, включая:

1. Если , то (упр. 9 в конце параграфа).

2. Если , то или (упр. 10 в конце параграфа).

3. Если , то (упр. 11 в конце параграфа).

Теорема А.3.7. Если задано формулой (А.6), то является метрикой на пространстве К. всех непустых компактных подмножеств .

Доказательство.

1. . Это немедленно следует из определения (А.6), так как величины неотрицательны.

2. тогда и только тогда, когда . Если , то, очевидно, . С другой стороны, если , то В соответствии с пунктом 2, предшествовавшим теореме, мы должны получить .

3. . Это утверждение следует непосредственно из определения .

4. для любых , (неравенство треугольника). Во-первых, покажем, что для любых :

и

Для этого нам потребуется следующая элементарная формула (упр. 7 в конце параграфа):

Тогда

Докажем неравенство . Неравенство доказывается аналогично. Пусть . Тогда

Для каждого

Так как это неравенство верно при любом , то

Рассмотрим, как можно использовать метрику Хаусдорфа. Пусть (X, d) — метрическое пространство. Напомним, что последовательность из X сходится к точке в -метрике, если

Если «точки» — непустые компактные множества и Е, причем используется метрика Хаусдорфа, то утверждение о сходимости принимает вид:

На практике определить расстояние Хаусдорфа между двумя множествами бывает непросто. К счастью, имеется альтернативный подход, позволяющий глубже понять метрику Хаусдорфа. Он связан с понятием расширения (дилатации), введенным в п. 3.5.

Для заданного множества Е в и радиуса расширение Е радиуса обозначаемое как , определяется как векторная сумма где — замкнутый шар радиуса с центром в начале координат (рис. 3.2). Это можно записать и в следующем эквивалентном виде:

Предостережение: в некоторых книгах расширения определяются с помощью открытых шаров, в то время как мы используем замкнутые шары. Наше предпочтение связано с незначительным упрощением доказательства следующей теоремы.

Теорема . Пусть Е и F — компактные подмножества Расстояние Хаусдорфа удовлетворяет соотношению:

Доказательство. Мы покажем, что в том и только в том случае, если .

Из соображений симметрии такое же рассуждение приводит к тому, что в том и только в том случае, если . Предположим, что . Тогда для любой точки имеем откуда следует, что . Поэтому .

Обратно, если , тогда для каждой точки существует точка такая, что Из этого следует, что для всех и поэтому

Следствие А.3.3. Пусть — компактные множества. Тогда в метрике Хаусдорфа в том и только в том случае, если для каждого существует такой номер N, что из следует

Следствие . Пусть — непустые компактные множества, упорядоченные по убыванию:

Пусть

Тогда Е непусто и компактно, и существует предел

в метрике Хаусдорфа.

Доказательство. Множество Е непусто и компактно вследствие стандартной теоремы о компактных множествах [42]. В соответствии со следствием надо показать, что для любого существует целое N такое, что из следует

Так как множества упорядочены по убыванию, то а значит нам необходимо рассмотреть только первый случай. Множество будучи объединением шаров, открыто и содержится в .

В соответствии с упр. 12 в конце параграфа, если пересечение последовательности упорядоченных по убыванию компактных множеств содержится в открытом множестве, то компактные множества сами содержатся в открытом множестве. Таким образом, компактные множества содержатся в .

Данное следствие имеет непосредственное отношение к фракталам, которые образуются последовательным устранением открытых множеств. Например, это классическое множество Кантора, получаемое последовательным выбрасыванием открытых срединных третей интервалов. Используя это следствие, получаем, что аппроксиманты (рис. 2.20) сходятся к множеству Кантора в метрике Хаусдорфа. В качестве другого примера можно привести построение ковра Серпинского (рис. 2.5).

Теорема А.3.9. Пусть К. есть совокупность всех непустых компактных подмножеств , а Н — метрика Хаусдорфа. Тогда метрическое пространство полное.

Доказательство. Пусть — последовательность множеств в которая удовлетворяет критерию Коши для метрики Хаусдорфа. По упр. 3 из прил. А.1, существует такая константа М, что при и поэтому

Зададим

Тогда являются замкнутыми и ограниченными, а следовательно, компактными подмножествами . Пусть

Так как множества упорядочены по убыванию, то из следствия А.3.4 вытекает, что в метрике Хаусдорфа при Мы покажем, что Е также является пределом исходной последовательности в метрике Хаусдорфа, то есть

Пусть Существует целое такое, что из следует

В частности, из второго условия при следует

то есть . Так как удовлетворяет критерию Коши в метрике Хаусдорфа, то существует такое целое что из следует

Зафиксируем При любом получим

Таким образом, если то и формула (А.9) доказана.

Теорема А.3.10. Если А — компактное подмножество — совокупность всех непустых компактных подмножеств А, то метрическое пространство где Н — метрика Хаусдорфа, компактно.

Упражнения 1.3.

1. Пусть 5 — периметр квадрата с вершинами (0,1), (1,0), (1,1) и (0,1). Нарисуйте расширение используя манхэттенскую метрику на Сравните результат с ответом к упр. 3.5.1.

2. Найдите расстояние Хаусдорфа Н(А,В) в пространстве, оснащенном манхэттенской метрикой:

Сравните результат с ответом к упр. 3.5.2.

3. Пусть — манхэттенская метрика на Вычислите , где — точка (1,1),

4. Рассмотрим диск Положим, что решетка с размером ячеек накрывает D, а начало координат решетки совпадает с центром диска. Пусть есть наименьшее множество, представляющее собой объединение квадратов решетки, накрывающих

а) Покажите, что расстояние Хаусдорфа Н, использующее евклидову метрику, обладает свойством:

б) Покажите, что периметр множества удовлетворяет неравенству Как это связано с длиной окружности D в махэттенской метрике?

5. Покажите, что если Е компактно в то

6. Покажите, что если компактны в то всегда существуют такие точки , что

7. Покажите, что (а )

8. Покажите, что если , то Более того, если

9. Покажите, что если и

10. Покажите, что если , то или .

11. Предположим, что E, F и G суть компактные множества в с евклидовой метрикой. Покажите, что

12. Убедитесь в верности следствия Если множество Е является пересечением компактных множеств и содержится в открытом множестве G, то при всех достаточно больших .

13. Покажите, что для