Оптимальное положение компактов в пространствах с евклидово инвариантной метрикой Громова-Хаусдорфа (1162480), страница 2
Текст из файла (страница 2)
Вчастности, dEGH (A, B) = 21 |d(A1 , A2 ) − d(B1 , B2 )|.Для доказательства следствия будем пользоваться следующей леммой.Лемма 2.7. Пусть I = [P, Q] ⊂ Rd — произвольный отрезок и Br (I) — его замкнутаяr-окрестность. Тогда множество Br (I) выпукло, и для любых C, D ∈ Br (I) выполняетсяd(C, D) ≤ d(P, Q) + 2r, причем равенство имеет место тогда и только тогда, когда [C, D] —отрезок длины d(P, Q) + 2r, лежащий на прямой P Q, а его середина совпадает с серединойI.Доказательство.
Окрестность отрезка наименьшей длины — это цилиндр, к основаниям которого прикреплены полушары с центрами в концах отрезка. Так как все точки этой окрестностиудалены от точек отрезка не более, чем на r, то для точки C существует точка P 0 ∈ [P Q],такая что d(C, P 0 ) ≤ r, и для D существует Q0 ∈ [P Q] такая, что d(D, Q0 ) ≤ r. Тогдаd(C, P 0 ) + d(P 0 , Q0 ) + d(Q0 , D) ≤ 2r + d(P 0 , Q0 ) ≤ 2r + d(P, Q). В последнем неравенстве равенство достигается, когда {P 0 , Q0 } = {P, Q}; не ограничивая общности, P = P 0 и Q = Q0 .Тогда, в этом предположении, получаем d(C, D) ≤ 2r + d(P, Q), где равенство достигается,когда d(C, P ) = d(D, Q) = r. Осталось заметить, что величина d(C, D) может принимать этомаксимальное значение, и это происходит в точности тогда, когда точки и D лежат на пересечении прямой, содержащей I, и граничных сфер окрестностей Br (P ) и Br (Q).
Это и означает,что отрезки [P, Q] и [C, D] лежат на одной прямой, и их середины совмещены.Теперь обратимся к следствию 2.6.Доказательство. Пусть 2R = d(A1 , A2 ) ≥ d(B1 , B2 ) = 2r. Покажем, что описанное в предложении положение оптимально. По лемме 2.7, отрезок наибольшей длины можно движениямипоместить в окрестность второго отрезка, только когда ее радиус не меньше полуразности6отрезков. В таком положении dH (A, B) ≥ R − r. Обратно, расстояние между любыми двумяточками A01 и A02 из (R − r)-окрестности компакта B не превосходит 2R, опять же по лемме2.7, и это расстояние достигается, только когда точки A01 и A02 лежат на прямой, содержащей[B1 , B2 ], и середины отрезков [B1 , B2 ] и [A01 , A02 ] совпадают.
Значит, отрезок [A01 , A02 ] — эторезультат движения отрезка той же длины [A1 , A2 ], и других оптимальных взаимных расположений отрезков [B1 , B2 ] и [A1 , A2 ] не существует.Предложение 2.8. Оптимальное положение шаров A и B одинаковой максимальной размерности — это совмещение их центров.Доказательство. Будем считать, что радиус шара A равен R, радиус шара B равен r и R > r.Совместим центры шаров, тогда dH (A, B) = R − r. Пусть существует иное положение шаров,при котором расстояние между ними не увеличивается.
Пусть при этом d(O1 , O2 ) = ε >0, где O1 и O2 — центры A и B соответственно. Пусть N — та из двух точек пересеченияграницы шара A и прямой O1 O2 , которая находится дальше от O2 . Тогда ближайшая к Nточка компакта B — это точка M из пересечения прямой O1 O2 с границей шара B (та, котораялежит на отрезке [N, O2 ]). Тогда dH (A, B) ≤ d(M, N ) = R + ε − r > R − r. Противоречие.Значит, больше оптимальных положений нет, и единственное возможное — это совмещениецентров.Во всех вышеописанных примерах мы видим, что оптимальное положение компактов —это совмещение чебышевских центров.
Возникает вопрос: всегда ли это так? Рассмотрим ещеодин пример оптимального положения, дающий отрицательный ответ на этот вопрос.Предложение 2.9. Рассмотрим трехточечный компакт A = {A1 , A2 , A3 } и двухточечныйкомпакт B = {B1 , B2 }, где d(B1 , B2 ) = d. Пусть a3 = d(A1 , A2 ), a1 = d(A2 , A3 ), a2 =d(A3 , A1 ) и a1 ≤ a2 ≤ a3 , точка M — середина [A2 , A3 ]. Пусть d(M, A1 ) ∈ [d − a21 , d + a21 ].Тогда оптимальное взаимное расположение компактов A и B описывается, с точностью донумерации точек компакта B, следующим образом:1) если a1 < a2 ≤ a3 , то B1 необходимо поместить в середину [A2 , A3 ], а B2 — в кругB a21 (A1 );2) если a1 = a2 < a3 , то B1 нужно поместить или в середину [A2 , A3 ], или в середину[A1 , A3 ], а B2 нужно соответственно поместить в круг B a21 (A1 ) или B a21 (A2 );3) если a1 = a2 = a3 , то B1 нужно поместить в середину любой стороны [Ai , Aj ], а B2— в “оставшийся круг” B a21 (Ak ), {i, j, k} = {1, 2, 3}.7Доказательство.
Покажем, что расстояние по Хаусдорфу между компактами A и OB, где O— некоторое движение плоскости, сохраняющее ориентацию, не может быть меньше a1 /2.Предположим противное, т.е. что dH (A, OB) < a21 , и выберем произвольное ε такое, чтоdH (A, OB) < ε < a21 . Тогда Bε (A) = ∪3i=1 Bε (Ai ) ⊃ OB. Так как круги Bε (Ai ) не пересекаются,один из них, скажем, Bε (Ak ), не содержит точек из OB. Но тогда Ak 6∈ Bε (OB), противоречие.Таким образом, dEGH (A, B) ≥ a21 .
С другой стороны, для каждого описанного в формулировкепредложения взаимного расположения компактов A и B имеем dH (A, B) = a21 , так что для всехтаких компактов B выполняется dEGH (A, B) = a21 , поэтому все эти взаимные расположениякомпактов A и B оптимальны.Покажем теперь, что других оптимальных расположений нет. Заметим, что при оптимальном взаимном расположении компактов A и B, две точки B1 и B2 должны содержаться вовсех трех шарах Ba1 /2 (Ai ). Это означает, что одна из точек, скажем B1 , должна быть общейу двух шаров.
Тогда она — точка касания этих шаров, а касание происходит только в середине стороны треугольника, длина которой равна a1 . Если такая сторона одна, то необходимопоместить B1 в ее середину. Если таких сторон длины a1 две или три, поместим B1 в середину любой из них. Заметим, что при каждом выборе расположения точки B1 вторая точкаB2 может быть помещена в оставшийся шар в силу условия на длину отрезка [B1 , B2 ].
Внеоставшегося шара точку B2 поместить нельзя, иначе расстояние по Хаусдорфу будет больше,чем a1 /2. Таким образом, всегда реализуется один из описанных случаев предложения.Замечание 2.10. В указанной конструкции чебышевский центр компакта A совсем не обязанлежать на отрезке [M, A1 ], где лежит чебышевский центр компакта B, поэтому, вообще говоря,чебышевские центры компактов A и B не совпадают.Замечание 2.11. Приведенный только что пример оптимального положения также являетсяпримером, когда оптимальное положение не единственно, их даже континуум.Приведем еще один пример, показывающий, что оптимальное положение компактов — необязательно совмещение чебышевских центров.8Предложение 2.12.
Положение n-мерного шара B радиуса r и отрезка A = [A1 , A2 ], длинакоторого не превышает диаметр шара 2r, оптимально, если и только если оно представляетсобой совмещение центра шара с некоторой точкой отрезка.Доказательство. Окрестность отрезка в Rn — это цилиндр, к основаниям которого прикреплены полушары с центрами в концах отрезка.
Следовательно, если поместить центр шара Bна отрезок A, то шар B окажется в r-окрестности отрезка A. Кроме того, в силу предположения на соотношение между длиной отрезка A и диаметром шара B, при таком расположенииотрезок A окажется в r-окрестности шара B, так что расстояние Хаусдорфа между такими Aи B равно r.
С другой стороны, если центр шара B не лежит на A, то шар B не попадает вr-окрестность отрезка A (см. доказательство предложения 2.8), поэтому между такими A и Bрасстояние Хаусдорфа больше r.При этом, совмещение чебышевских центров компактов в последнем примере также даетоптимальное положение.Предложение 2.13. Пусть даны компакты A = [A1 , A2 ] и B — n-мерный шар радиуса r.Тогда dEGH зависит от длины отрезка: при d(A1 , A2 ) ≤ 4r имеем dEGH (A, B) = r, приd(A1 , A2 ) ≥ 4r выполняется dEGH (A, B) = 12 d(A1 , A2 ) − r. При этом, в первом случае положение компактов A и B оптимально, если и только если центр шара B находится наотрезке A так, что длина каждой связной компоненты множества A \ B не превышаетr. Во втором случае положение компактов A и B оптимально, если и только если центршара B лежит в середине отрезка A.Доказательство.
Если d(A1 , A2 ) ≥ 4r, покажем, что dEGH (A, B) = 12 d(A1 , A2 ) − r. Предположим, существует движение плоскости O, сохраняющее ориентацию, такое, что dH (A, OB) =d < 12 d(A1 , A2 )−r. Значит, A ⊂ Bd (B). Так как d-окрестность шара — это шар с тем же центромрадиуса r+d, то максимальная длина отрезка, который может содержаться в этом шаре, равна2(r + d) < d(A1 , A2 ) — противоречие. Значит, dH (A, OB) ≥ 12 d(A1 , A2 ) − r, где равенство достигается, если поместить центр шара в середину отрезка, поэтому dEGH (A, B) = 12 d(A1 , A2 ) − r,и указанное расположение компактов оптимально.
Оно единственно, так как если A и B находятся в оптимальном положении, и d = dH (A, B), то, как мы только что показали, длинаотрезка [A1 , A2 ] равна диаметру шара Bd (B), а такой отрезок содержится в этом шаре, еслии только если его середина — центр шара.Пусть d(A1 , A2 ) ≤ 4r. Предположим, существует движение плоскости O, сохраняющее ориентацию, такое, что dH (A, OB) = d < r. Значит, B ⊂ Bd (A). Так как d-окрестность отрезка —это цилиндр, к основаниям которого прикреплены полушары с центрами в A1 и A2 и радиусаd, то максимальный радиус шара, который можно поместить в эту окрестность, равен d, противоречие. Значит, dH (A, OB) ≥ r, где равенство достигается, если поместить центр шара внекоторую точку отрезка так, чтобы длины отрезков [Ai , Ci ], где Ci — соответственные точкипересечения A и граничной сферы шара B, не превышали r.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
