Оптимальное положение компактов в пространствах с евклидово инвариантной метрикой Громова-Хаусдорфа (1162480), страница 3
Текст из файла (страница 3)
Поэтому dEGH (A, B) = r, и указанное расположение компактов оптимально. Других оптимальных положений нет, так какесли центр шара B не лежит на прямой, содержащей отрезок [A1 , A2 ], то шар не попадает в rокрестность отрезка. Иначе dEGH (A, B) = r, если и только если A содержится в r-окрестностиB, т.е. длины отрезков [Ai , Ci ] не превосходят r.9В работе С. Илиадиса, А.О.Иванова и А.А.Тужилина [9] показано, как можно изометрично вложить конечное метрическое пространство в пространство Громова-Хаусдорфа. Тот жевопрос о счетных метрических пространствах остается открытым, как и вопрос реализацииметрических пространств в евклидовых пространствах с метрикой Громова-Хаусдорфа.
Мыпокажем, как это сделать для трехточечного пространства.Предложение 2.14. Рассмотрим пространство {M1 , M2 , M3 } с заданными расстояниямиd(M2 , M3 ) = a, d(M1 , M3 ) = b, d(M1 , M2 ) = c, a ≥ b ≥ c. Тогда в качестве реализацииданного пространства в пространстве Ho (Rn ), n ≥ 2, наделенном метрикой dEGH , можновзять отрезок A = [A1 , A2 ] длины 2(a + b), шар B радиуса b и отрезок C = [C1 , C2 ] длины2(a + b − c). Множества A, B и C можно разместить в Rn так, чтобы для каждой пары изних это положение было оптимальным. Все такие положения описываются так : отрезкиA и C лежат на одной прямой и их центры совпадают; наибольший из этих отрезковрасположен так, как описано в предложении 2.13.Доказательство.
Так как из неравенства треугольника a − c ≤ b следует 2(a + b − c) ≤ 4b,а из условия a ≥ b следует 2(a + b) ≥ 4b, то по предложению 2.13 имеем dEGH (A, B) = a,dEGH (B, C) = c, а из следствия 2.6 вытекает, что dEGH (A, C) = b. Eсли три компакта расположены так, что каждая пара из них находится в оптимальном положении, то отрезки должныбыть совмещены так, чтобы они были на одной прямой и совпали их середины (следствие 2.6),шар и отрезок наибольшей длины — так, как описано в формулировке предложения 2.13. Таким образом, положения, которые описаны в формулировке текущего предложения, и толькоони — оптимальны.102.1Об оптимальном положении компактов, находящихся в положении “между”Теорема 1.
Пусть непустые компакты A и B находятся в оптимальном положении. Тогдавсе компакты между A и B в смысле метрики Хаусдорфа, в паре с каждым из компактовA и B, — тоже в оптимальном положении в смысле евклидово инвариантной метрикиГромова–Хаусдорфа.Доказательство. Так как A и B находятся в оптимальном положении, то, по определению,dH (A, B) = dEGH (A, B). Так как расстояние dEGH является метрикой, то из неравенства треугольника следует, чтоdEGH (A, B) ≤ dEGH (A, C) + dEGH (C, B);опять же, из оптимальности положения, заключаемdEGH (A, C) ≤ dH (A, C), dEGH (C, B) ≤ dH (C, B).Если компакт C оказался не в оптимальном положении относительно A или B, то одно издвух предыдущих неравенств будет строгим, поэтому, в этом случае,dH (A, B) = dEGH (A, B) ≤ dEGH (A, C) + dEGH (C, B) < dH (A, C) + dH (C, B),следовательно, C не находится между A и B, противоречие.
Значит, компакты A и C, B и Cнаходятся в оптимальном положении.Замечание 2.15. Обратное не верно, как показывает предложение 2.14.Замечание 2.16. Транзитивность не верна: если компакты A и B, B и C находятся в оптимальном положении, компакты A и C не обязаны находиться в оптимальном положении.Например, пусть A = {A1 , A2 }, B = {B1 }, C = {C1 , C2 }. Совместим середины компактов A иC, при условии, что точки A1 , A2 , C1 , C2 не лежат на одной прямой, а компакт B поместим вих общую середину. Таким образом, одноточечный компакт в оптимальном положении с каждым из двухточечных, но между собой двухточечные не находятся в общем положении.
Болеетого, не любые 3 компакта удается разместить так, чтобы любые два оказались в оптимальномположении. Возьмем пример, описанный в предложении 2.9.Пусть множество A ⊂ R2 состоит из трех точек, попарные расстояния между которымиравны 10, 13, 13; множество B ⊂ R2 — из двух точек на расстоянии 10; множество C ⊂ R2— из одной точки. Предположим, что эти три множества расположены так, что из взаимныепопарные расположения — оптимальны. По предложению 2.2, множество C совпадает с чебышевским центром множеств A и B, однако, для A чебышевский центр — это центр описаннойокружности, так что если M обозначает середину основания равнобедренного треугольникас вершинами в A, то d(C, M ) = 119/24.
По предложению 2.9, одна из точек множества Bсовпадает с M , поэтому, снова в силу предложения 2.2, точка C попадает в середину отрезкас концами в B, следовательно, d(C, M ) = 5, противоречие.112.2Об оптимальном положении ориентированно подобных компактовОбращаясь к вопросу о совмещении чебышевских центров, хочется понять, в каких случаяхэто решает проблему поиска оптимального положения. В качестве примера разберем случай,когда компакты отличаются на подобие, сохраняющее ориентацию.Приведем несколько вспомогательных результатов. Для каждого X ∈ H(Rn ) через OX иRX будем обозначать его чебышевские центр и радиус.Лемма 2.17. Для произвольного X ∈ H(Rn ) и ε > 0 имеем Bε (X) ⊂ BRX +ε (OX ).Доказательство.
Так как все точки компакта X удалены от OX не более, чем на RX , то точкикомпакта Bε (X) удалены от OX не более, чем на RX + ε в силу неравенства треугольника. Ноэто и означает, что Bε (X) ⊂ BRX +ε (OX ).Лемма 2.18. Пусть X ∈ H(Rn ) и λ > 0. Тогда у компакта Y = OX + λ(X − OX ), гомотетичного X, чебышевские центр и радиус — это OX и λRX .Доказательство. Для каждой точки y ∈ Y выполнено y = OX + λ(x − OX ) для некоторогоx ∈ X. Так как λ|x − OX | ≤ λRX , то и для любого y ∈ Y верно, что d(y, OX ) ≤ λRX .
ПоэтомуRY ≤ λRX . Применяя те же рассуждения для точек из X, заключаем, что RX ≤ λ1 RY . Значит,RY = λRX . Отсюда, в силу единственности чебышевского центра у компактных подмножествRn , следует, что OX является чебышевским центром компакта Y .Лемма 2.19. Если для X, Y ∈ H(Rn ) выполнено RY = RX + ε, ε > 0, то для любого 0 < δ < εи для любого движения M имеем M (Y ) 6⊂ Bδ (X).Доказательство.
По лемме 2.17, имеем Bδ (X) ⊂ BRX +δ (OX ). Но так как RY = RX + ε, токомпакт Y ни в какой шар меньшего радиуса поместить нельзя, то есть M (Y ) 6⊂ BRX +δ (OY ) нидля какого 0 < δ < ε и движения M . Но тогда M (Y ) 6⊂ Bδ (X), что и требовалось доказать.Лемма 2.20. Для X ∈ H(Rn ) и ε > 0 имеем RBε (X) = RX + ε и OBε (X) = OX .Доказательство. Из леммы 2.17 следует, что RBε (X) ≤ RX + ε. Покажем, что RBε (X) ≥RX + ε. Пусть существует шар с центром в некоторой точке O радиуса RX + δ, где 0 < δ < ε,такой, что Bε (X) ⊂ BRX +δ (O).
Тогда для произвольной точки x ∈ X выполнено d(O, x) + ε ≤RX + δ, то есть d(O, x) ≤ RX + δ − ε < RX . Это означает, что нашлась такая точка O, чтовсе точки из X удалены от O на расстояние, меньшее RX , то есть RX — не чебышевскийрадиус. Противоречие. Итак, RBε (X) = RX + ε. Отсюда же следует, что OX = OBε (X) (в силуединственности чебышевского центра у компактных подмножеств Rn ).Лемма 2.21. Если для X, Y ∈ H(Rn ) таких, что RY = RX + ε, ε > 0, чебышевские центрыне совпадают, то Y 6⊂ Bε (X).Доказательство. Так как OX 6= OY , то чебышевские шары BRX +ε (OX ) и BRY (OY ) для Bε (X)и для Y соответственно имеют одинаковые радиусы (лемма 2.20) и разные центры, то естьшары не совпадают.
С другой стороны, если Y ⊂ Bε (X), то Y ⊂ BRX +ε (OX ) ∩ BRY (OY ), ноправая часть последнего включения, являясь пересечением несовпадающих шаров одинакового радиуса RY , содержится в шаре меньшего чем RY радиуса. Последнее противоречит тому,что RY — чебышевский радиус для Y . Значит, Y 6⊂ Bε (X).12Лемма 2.22. Пусть X, Y ∈ H(Rn ) — ориентированно подобные компакты.
ТогдаdEGH (X, Y ) = |RY − RX |.Доказательство. Пусть S = Λ ◦ M — сохраняющее ориентацию подобие, для которого Y =S(X), где Λ — растяжение в λ > 0 раз с центром в O, а M ∈ G. Отметим, что RY = λRX .Если λ = 1, то RX = RY и dEGH (X, Y ) = 0, так что в этом случае утверждение леммыверно.Пусть теперь λ 6= 1. Без ограничения общности, будем считать, что λ > 1, тогда |RY −RX | =RY − RX = (λ − 1)RX .
Кроме того, так как центр O соответствующего растяжения можновыбирать произвольным образом, поместим его в чебышевский центр OX компакта X. Тогдадля λ-гомотетичных компактов X и M (Y ) расстояние между точкой x ∈ X и соответствующейточкой y = O + λ(x − O) ∈ M (Y ) равно d(x, y) = (λ − 1)d(x, O), поэтомуdH X, M (Y ) ≤ (λ − 1) supx∈X d(x, O) ≤ (λ − 1)RX = RY − RX ,и, значит, dEGH (X, Y ) ≤ RY − RX . Покажем, что на самом деле здесь имеется равенство.Предположим противное, т.е. что dEGH (X, Y ) < RY − RX . Тогда существуют δ такое, что0 < δ < RY − RX , и движение M 0 такие, что M 0 (Y ) ⊂ Bδ (X).
Но, по лемме 2.19, RY ≤ RX + δ.Противоречие.Теорема 2. Пусть X и Y — непустые ориентированно подобные компакты в Rn . ТогдаdEGH (X, Y ) = |RY − RX |, и если эти компакты находятся в оптимальном положении, тоих чебышевские центры совпадают. Более того, положение, в котором OX = OY , а X и Y— гомотетичны с центром в OX , является оптимальным.Доказательство. То, что dEGH (X, Y ) = |RY − RX |, является утверждением леммы 2.22. Далее, предположим, что X и Y находятся в оптимальном положении. По лемме 2.21, если ихчебышевские центры не совпадают, то dH (X, Y ) > |RY − RX |, что противоречит оптимальности.
Наконец, пусть OX = OY и рассматриваемые компакты гомотетичны с центром в OX .Аналогично тому, что было сделано при доказательстве леммы 2.22, dH (X, Y ) ≤ |RY − RX |,поэтому такие X и Y находятся в оптимальном положении.Замечание 2.23. Совпадающие чебышевские центры ориентированно подобных компактов,находящихся в оптимальном положении, не обязаны совпадать с центром гомотетии: еслиX — это две окружности с одним центром O (граница кольца), соединенные отрезком, а Y— гомотетичное множество с центром в O, то указанное положение — оптимально.
Но есливращать Y относительно O, то расстояние по Хаусдорфу не изменится.13Список литературы[1] Edwards D. The Structure of Superspace. In «Studies in Topology». Academic Press, 1975.[2] Gromov M. Groups of Polynomial growth and Expanding Maps. Publications mathematiques,53, 1981.[3] Бураго Д.Ю., Бураго Ю.Д., Иванов С.В. Курс метрической геометрии. Москва-Ижевск,Институт компьютерных исследований, 2004.[4] Гаркави А.Л.
О чебышевском центре и выпуклой оболочке множества. Успехи матем.наук, 1964, т. 19, вып. 6, с. 139-145.[5] Казаков А.Л., Лебедев П.Д. Построение наилучших круговых аппроксимаций множествна плоскости и на сфере. XII Всероссийское совещание по проблемам управления ВСПУ2014, Москва 16-19 июня 2014 г.[6] Сосов Е.Н. Геометрии выпуклых и конечных множеств геодезического пространства.Казанский Государственный Университет, 2010.[7] Facundo Memoli.
Gromov–Hausdorff distances in Euclidean spaces. Computer Vision andPattern Recognition Workshops, 2008. CVPR Workshops 2008. IEEE Computer SocietyConference on, pages 1–8, June 2008.[8] Кисловская А.Д. Дипломная работа “Геометрия конфигураций в пространствах с евклидово инвариантной метрикой типа Громова–Хаусдорфа”. Москва, Московский Государственный Университет, 2013.[9] Iliadis S., Ivanov A., Tuzhilin A. Local Structure of Gromov–Hausdorff Space, and IsometricEmbeddings of Finite Metric Spaces into this Space. Topology and its Applications, ElsevierBV, Netherlands, 2017, v. 221, pp. 393-398, DOI: 10.1016/j.topol.2017.02.050 (см. также ArXive-prints, arXiv:1604.07615).14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
