САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Математико-механический факультет
Кафедра математической физики
Теплицкая Яна Игоревна
Гипотеза подковы для минимайзера максимального расстояния
Выпускная квалификационная работа
Специальность 01.01.02 — «Дифференциальные уравнения, динамические системы и оптимальное управление»
Научный руководитель:
д. ф.-м. н., профессор Степанов E.О.
Рецензент:
д. ф.-м. н., профессор Малютин А.В.
Санкт-Петербург
2016
SAINT PETERSBURG STATE UNIVERSITY
Mathematics and Mechanics Faculty
Department of the partial differential equations
Teplitskaya Yana
On the horseshoe conjecture
in the optimal pipeline problem
Graduation Qualification Paper
Scientific supervisor:
professor Eugene Stepanov
Reviewer:
professor A. V. Malyutin
Saint Petersburg
2016
Содержание
1. Аннотация выпускной квалификационной работы
2. Введение
3. Основные результаты
3.1. Схема доказательства
4. Доказательства
4.1. Доказательство центральной Леммы
5. Заключение
Список литературы
3
3
4
5
9
13
17
17
1. Аннотация выпускной квалификационной работы
Мы изучаем свойства множеств Σ, обладающих минимальной длиной (одномерной мерой Хаусдорфа) в классе замкнутых связных множеств Σ ⊂ R2 , удовлетворяющих неравенству
max dist (y, Σ) ≤ r
y∈M
для заданного компактного множества M ⊂ R2 и для заданного числа r > 0. Такие множества можно
воспринимать как водопроводы минимальной длины, подходящие на расстояние не более r к каждой
точке множества M , которое можно считать множеством потребителей воды.
В настоящей работе доказывается гипотеза Миранды, Паолини и Степанова, описывающая множество минимайзеров для частного случая, когда M является окружностью радиуса R > 0, удовлетворяющего условию r < R/4.98. Более того, мы показываем, что если M является границей гладкого
выпуклого множества с минимальным радиусом кривизны R, то любой минимайзер Σ имеет схожую
структуру при условии r < R/5. Кроме того, мы доказываем схожее утверждение для локальных
минимайзеров.
2. Введение
Для заданного компактного множества M ⊂ R2 рассмотрим функционал
FM (Σ) := max dist (y, Σ),
y∈M
где Σ — замкнутое подмножество R2 и dist (y, Σ) обозначает евклидово расстояние между y и Σ. Величина FM (Σ) будет в дальнейшем называться энергией множества Σ. Рассмотрим класс замкнутых
связных множеств Σ ⊂ R2 , удовлетворяющих неравенству FM (Σ) ≤ r для некоторого r > 0. Нас интересуют свойства множеств минимальной длины (одномерной меры Хаусдорфа) H1 (Σ). В дальнейшем
будем называть такие множества минимайзерами. Такие множества можно воспринимать как водопроводы минимальной длины, подходящие на расстояние не более r к каждой точке множества M ,
которое можно считать множеством потребителей воды.
∗
В работе [10] доказано (даже для общего n-мерного случая M ⊂ Rn ), что множество OP T∞
(M )
минимайзеров (для всех r > 0) непусто и совпадает с множеством OP T∞ (M ) решений двойственной
задачи: минимизировать FM среди всех компактных связных множеств Σ ⊂ R2 с заданным ограничением на длину H1 (Σ) ≤ l (для соответствующего l > 0). Вышеупомянутая двойственная задача
сходна с большим числом задач минимизации других функционалов на классе замкнутых связных
множеств, к примеру функционала среднего расстояния относительно некоторой конечной борелевской меры (см [3], [5], [6], [9] and [8]) или близких к ним задач городского планирования (см [4]).
Минимизация функционала максимального или среднего расстояния среди дискретных множеств
с заданным ограничением на число компонент связности (а не среди связных одномерных множеств)
приводит к классу близких задач: k-center problem и k-median problem (см, например, [12], [13], [7] а
также [2, 1] и ссылки там).
Некоторые базовые свойства минимайзеров для введенной выше задачи в общем, n-мерном случае
(такие как отсутствие петель или регулярность по Альфорсу), доказаны в [11]. Пусть в дальнейшем
3
Br (x) обозначает открытый шар с радиусом r и центром в точке x, а Br (M )— открытую r-окрестность
M , то есть
[
Br (M ) :=
Br (x).
x∈M
Введем следующие естественные понятия.
Определение 2.1. Точка x ∈ Σ называется энергетической, если для произвольного ρ > 0 выполняется
FM (Σ \ Bρ (x)) > FM (Σ).
Множество всех энергетических точек Σ будем обозначать GΣ .
∗
Рассмотрим минимайзер Σ ∈ OP T∞
(M ) с энергией r = FM (Σ). Тогда множество Σ может быть
разбито на три непересекающихся множества:
Σ = EΣ t XΣ t SΣ ,
где XΣ ⊂ GΣ — множество изолированных энергетических точек (то есть каждая точка x ∈ XΣ —
энергетическая и найдется такое ρ > 0, возможно зависящее от x, что Bρ (x)∩GΣ = {x}); а EΣ = GΣ \XΣ
— множество неизолированных энергетических точек. В [10] доказаны следующие утверждения.
(a) Для любой точки x ∈ GΣ найдется такая точка y ∈ M , что |x − y| = r и Br (y) ∩ Σ = ∅. Если
XΣ не конечно, тогда точки сгущения XΣ принадлежат EΣ .
(b) Для произвольной x ∈ SΣ найдется такое ε > 0, что SΣ ∩ Bε (x) является отрезком или правильной треногой, то есть объединением трех отрезков с концевой точкой в x и попарными углами
величины 2π/3.
(c) XΣ относительно открыто в GΣ .
В дальнейшем мы будем использовать следющие обозначения.
Определение 2.2. Для выпуклого замкнутого множества N определим минимальный радис кривизны его границы с помощью формулы
R(∂N ) := inf sup{r : Br (O) ∩ ∂N = x для некоторого O ∈ N }.
x∈∂N
Определение 2.3. Для выпуклого замкнутого множества N мы определим внутреннее множество
Nr как множество всех точек N , лежащих на расстоянии хотя бы r от его границы: Nr := N \
Br (∂N ).
В дальнейшем будем обозначать N := conv (M ), где conv — выпуклая замкнутая оболочка, а Mr :=
∂Nr . Заметим, что N , Nr , M и Mr — замкнутые множества. Под замкнутой выпуклой кривой будем
понимать границу выпуклого множества.
Ясно, что если M — замкнутая выпуклая кривая с минимальным радиусом кривизны R > r, тогда
Mr — замкнутая выпуклая кривая с минимальным радиусом кривизны хотя бы R − r.
3. Основные результаты
Для заданных точек A, B будем использовать обозначения [AB], [AB) и (AB) для (замкнутого)
отрезка, луча и прямой соответственно.
Будем называть хордой замкнутой выпуклой кривой D отрезок, соединяющий две точки D. Подмножество q замкнутой выпуклой кривой D называется дугой D, если q является непрерывным инъективным образом отрезка (может совпадать с точкой). Образы концевых точек интервала будем называть
концами дуги, а образы внутренних точек интервала — внутренними точками дуги.
˘ а ее длину — |AB|
˘ (не
Когда ясно, о чем идет речь, дугу с концами A, B будем обозначать AB,
путать с длиной отрезка, соединяющего точки A и B, которая обозначается |AB|).
Мы говорим, что дуга q = Ql˘Qr множества Mr продолжается в множестве Σ хордой, если для
некоторого i ∈ {l, r} найдется хорда [Qi X] множества Nr такая, что [Qi X] ⊂ Σ. Будем говорить, что
множество A покрывает множество Q ⊂ M , если Q является подмножеством B̄r (A). Обычно последнее
обозначение мы используем для множества Q, являющегося дугой M .
4
Mr
M
Σ
Рис. 1. Подкова.
Определение 3.1. Пусть M — замкнутая выпуклая кривая с минимальным радиусом кривизны
R > r. Тогда связная кривая Σ называется подковой, если FM (Σ) = r и Σ — объединение дуги q
множества Mr и двух отрезков, касающихся множества Mr в различных концевых точках дуги q и
заканчивающихся энергетическими точками (как изображено на Рис. 1).
Следующая теорема доказывает гипотезу Миранды, Паолини и Степанова из работы [10] о множестве минимайзеров для M := ∂BR (0) при r < R/4.98. Она показывает даже больше. А именно, что
произвольная замкнутая выпуклая кривая M имеет минимайзеры схожей структуры, если минимальный радиус кривизны множества M составляет хотя бы 5r. Заметим, что это не доказывает гипотезу
целиком (которая в работе [10] была сформулирована для r < R).
Theorem 3.2. Для любой замкнутой выпуклой кривой M с минимальным радиусом кривизны R и
для произвольного r < R/5 множество минимайзеров содержит только подковы. Для окружности
M := ∂BR (O) утверждение верно при r < R/4.98.
Полезно заметить, что мы используем глобальную минимальность только в Лемме 3.5, Лемме 3.7 и
для неравенства m(S) ≤ 2 (Лемма 3.8). Во всех остальных шагах мы пользуемся только локальными
аргументами, поэтому можем что-то сказать также и о локальных минимайзерах.
Определение 3.3. Пусть M — выпуклая замкнутая кривая с минимальным радиусом кривизны R.
Множество Σ называется локальным минимайзером, если оно покрывает M и если найдется такое
ε > 0, что для произвольного множества Σ0 , покрывающего M и удовлетворяющего diam Σ∆Σ0 ≤ ε,
выполняется H1 (Σ) < H1 (Σ0 ).
Следствие 3.4. Пусть Σ — локальный минимайзер для некоторой замкнутой выпуклой кривой M с
минимальным радиусом кривизны R > 5r. Тогда найдется такая абсолютная константа c > 0, что
если Σ — не подкова, то H1 (Σ) − H1 (Σopt ) > c(R − 5r), где Σopt — (глобальный) минимайзер.
Отметим, что утверждение Теоремы 3.2 без требования соотношения на величины R и r, вообще
говоря, неверно (пример изображен на Рис. 2). В качестве контрпримера можно рассмотреть
N t := ∪x∈(0,t) Br (x), M t := ∂N t .
Заметим, что множество M t имеет минимальный радиус кривизны r для любого t. Если t r > 1, то
любая подкова имеет длину 2t − O(1), а ломаная X := ∪i=0...[t]+1 [xi , xi+1 ], где x2k = (−1, 2k), x2k+1 =
√
(1, 2k + 1) имеет длину 2t + o(1). Но множество X ∪ ∂Br ((0, 0)) ∪ ∂Br ((t, 0)) связно и покрывает M t .
3.1. Схема доказательства. Здесь мы приведем схему доказательства Теоремы 3.2. Для начала введем некоторые определения.
Обозначим за Σ произвольный минимайзер для некоторой выпуклой замкнутой кривой M . Будем
говорить, что дуга M замкнута, если она относительно замкнута в M .
Лемма 3.5. Пусть M — замкнутое выпуклое множество с минимальным радиусом кривизны R, а
Σ является минимайзером с энергией r < R. Тогда выполняются следующие утверждения.
5
A
|AB| = 2r
B
Mr
Σ2
Σ1
M
Рис. 2. Пример для ситуации без предположения R > 5r.
(i) Каждая связная компонента замыкания пересечения Σ с внутренностью Nr (далее будем
обозначать Σr ) является минимальной сетью для некоторого множества точек, лежащих
на Mr , то есть решением задачи Штейнера для этого множества, и, в частности, состоит
только из прямолинейных отрезков.
(ii) Σ состоит из дуг Mr и прямолинейных отрезков.
(iii) Существует такая функция r 7→ aM (r), что aM (r) ≤ 2r и длина любого отрезка Σ
qr не превосходит aM (r). Для окружности M := ∂BR (O) можно положить a∂BR (O) (r) = 2r
1−
r2
4R2 .
Замечание 3.6. Из Замечания 4.3 следует, что когда Σ ⊂ N является связным множеством, покрывающим M , таким, что H1 (Σ) ≤ H1 (Σopt ) + a, где Σopt — минимайзер, и с Σr , состоящим только из
прямолинейных отрезков, тогда длина каждого отрезка ∆ ⊂ Σr удовлетворяет неравенству
H1 (∆) ≤ 2r + a.
Подобное утверждение может быть доказано для M , являющегося границей не обязательно выпуклого множества, но мы будем рассматривать только выпуклый случай, чтобы избежать лишних
технических деталей.
Лемма 3.7. Пусть M — замкнутая выпуклая кривая с минимальным радиусом кривизны R >
2aM (r) + r, где aM определено в Лемме 3.5. Тогда множество Σr не имеет штейнеровских точек,
то есть состоит только из хорд кривой Mr .
Рассмотрим произвольную связную компоненту S множества Σ \ Nr и обозначим за n(S) число
энергетических точек множества S. Точки из S̄ ∩ Mr будем в дальнейшем называть точками входа S.
Обозначим число точек входа за m(S).
Следующая Лемма, в частности, показывает, что m(S) конечно.
Лемма 3.8. Пусть M — замкнутая выпуклая кривая с минимальным радиусом кривизны R >
2aM (r) + r. Пусть S — связная компонента множества Σ \ Nr . Тогда n(S) ≤ 2, m(S) ≤ 2. Более
того, S является локально минимальной сетью, соединяющей множество точек входа и энергетических точек множества S.
Замечание 3.9. Пусть Σ — локальный минимайзер в смысле Определения 3.3. Тогда ввиду Замечания 3.6 с a := (R − 5r)/4 каждый прямолинейный отрезок множества Σr := Σ ∩ Nr имеет длину не
превосходящую a0M (r) = 2r + (R − 5r)/4. Тогда, в Леммах 3.7 и 3.8, а также в Следствии 3.13 ниже, мы
можем заменить aM на a0M , а значит, они останутся верными при R > 2a0M (r) + r = 5r + (R − 5r)/2, а
значит и при R > 5r.
Заметим, что B̄r (S) ∩ M всегда является замкнутой дугой ввиду Леммы 3.8. Обозначим её за qS .
Лемма 3.10. В условиях Теоремы 3.2 каждая дуга множества Σ продолжается отрезками касательных к множеству Mr . То же верно и для Σ, являющегося локальным минимайзером в смысле
Определения 3.3 для выпуклой кривой M и r < R/5.
6
A
a
Sr0
Sl0
T
Qr
η = π/3
S
ν = π/3
Ql
qS
γ
Рис. 3. Иллюстрация к построению T .
Замечание 3.11. Как будет ясно из доказательства, для того чтобы утверждение Леммы 3.10 выполнялось для локальных минимайзеров, требование r < R/5 может быть немного ослаблено.
Лемма 3.12. Пусть M — выпуклая замкнутая кривая с минимальным радиусом кривизны R и пусть
Σ — минимайзер с энергией r < R. Тогда верны следующие утверждения.
(i) Пусть S1 , S2 — связные компоненты множества Σ \ Nr или дуги множества Σ ∩ Mr . Тогда
внутренности дуг qS1 и qS2 не пересекаются.
(ii) Σ не содержит петель (гомеоморфных образов S 1 ).
Следствие 3.13. Предположим, что множество Σ не содержит штейнеровских точек в Nr . Рассмотрим следющий абстрактный граф с вершинами, соответствующими связным компонентам
множества Σ \ Nr и дугам Σ ∩ Mr , и ребрами между ними, определенными следующим образом:
• две вершины, соответствующими связным компонентам множества Σ\Nr , связаны ребром,
если эти компоненты были связаны хордой Mr ,
• вершина, соответствуещая связной компоненте S множества Σ \ Nr , и вершина, соответствущая дуге C множества Σ ∩ Mr , связаны ребром, если S̄ ∩ C 6= ∅,
• вершины, соответствующие дугам Σ ∩ Mr , не связаны ребрами.
Этот граф является деревом и, более того, если R > 2aM (r) + r, то он является путем.
Доказательство. Лемма 3.12(ii) влечет отсутствие в графе циклов, а из Леммы 3.8 следует, что степень
вершин в этом графе не превосходит 2. Связность множества Σ влечет связность графа. Таким образом,
граф является путем в случае R > 2aM (r) + r.
Таким образом, в условиях Теоремы 3.2 существуют две компоненты связности множества Σ \ Nr ,
обладающие ровно одной точкой входа; эти компоненты соответствуют листьям нашего графа. Мы
7
будем называть их конечными компонентами и обозначать Sl и Sr (и называть их левой и правой
соответственно); остальные компоненты будем называть средними.
Граф, определенный в Следствии 3.13, который в условиях Теоремы 3.2 является путем, задает
на компонентах связности Σ \ Nr естественный порядок, начинающийся с Sl и заканчивающийся Sr .
Также он задает порядок на точках входа в каждой компоненте связности, первую из которых мы
будем называть левой, а последнюю — правой. Мы будем называть такой порядок порядком против
часовой стрелки.
Заметим, что дуги M , которые покрыты связными компонентами Σ \ Nr , смежными в графе, определенном в Следствии 3.13, являются соседними (то есть эти дуги имеют одну общую точку). А значит
дуги qSl и qSr тоже соседние.
Обозначим за A точку пересечения qSl и qSr (см Рис. 3); она существует, поскольку qSl и qSr —
замкнутые дуги, и единственна благодаря Лемме 3.12(i). Рассмотрим множество Σ̂ := Σ ∪ [ASl0 ] ∪
[ASr0 ], где [ASl0 ] и [ASr0 ] — отрезки длины r, соединяющие точку A с Sl и Sr соответственно. Ввиду
Леммы 3.12(ii) и того, что Br (A)∩Σ = ∅, множество Σ̂ ограничивает область, которую мы в дальнейшем
будем называть T (как изображено на Рис.3).
Предыдущие леммы влекут следующее следствие.
Следствие 3.14. Граница T — замкнутая кривая, состоящая из дуг Mr и прямолинейных отрезков.
Рассмотрим поведение касательной к границе области T . Следствие 3.14 и Лемма 3.10 гарантируют,
что все точки, где наклон касательной меняется, кроме точки A, принадлежат связным компонентам
Σ \ Nr или дугам Mr .
Определение 3.15. Пусть q кривая (не обязательно инъективная). Будем говорить, что поворот
кривой q это величина, определенная формулой:
Z b
wind(q) =
d arg(γ 0 (t)),
a
2
где γ : [a, b] → R — параметризация q и arg непрерывная ветка многозначной функции Arg. В нашей
постановке поворот почти всегда совпадает с углом между касательной линией и концами q.
Определение 3.16. Пусть S — компонента связности Σ \ Nr . Тогда wind(S) обозначает поворот
S ∩∂T , параметризованный против часовой стрелки. В частности, если S = Sl , то wind(S) означает
поворот соответствующей кривой S∩∂T , параметризованной так, чтобы начинаться в точке входа
и заканчиваться в Sl0 , а если S = Sr , то wind(S) означает поворот S ∩ ∂T , параметризованной так,
чтобы начинаться в Sr0 и заканчиваться в точке входа.
Для лучей [BC), [CD) мы будем использовать обозначение ∠([BC), [CD)) для направленного угла
от [BC) к [CD).
Теперь мы можем сформулировать центральную Лемму.
Лемма 3.17. Пусть M — выпуклая замкнутая кривая с минимальным радиусом кривизны R. Предположим, что r < R/5 (а для окружности M := ∂BR (O) достаточно выполнения условия r <
R/4.98). Путь S — связная компонента множества Σ \ Nr или дуга Mr . Тогда верны следующие
утверждения.
• Если S — средняя компонента или дуга Mr , то wind(qS ) ≤ wind(S). При этом равенство
достигается тогда и только тогда, когда S является дугой Mr .
• Если S — конечная компонента, тогда для правой и левой компонент выполняется
wind(qS ) ≤ wind(S) + ∠([CSl0 ), [Sl0 A)) + ∠([ASl0 ), a),
wind(qS ) ≤ wind(S) + ∠([CSr0 ), [Sr0 A)) + ∠(a, [ASr0 )),
где a обозначает касательный луч к M в точке A, направленный слева направо (см Рис. 3,
углы ∠([ASl0 ), a), ∠(a, [ASr0 )) обозначены красным), а C — точка ветвления, если S — тренога и точка входа, если S — отрезок (ввиду Леммы 3.8 других вариантов нет). Равенство
достигается тогда и только тогда, когда S — отрезок касательной к Mr .
8
Замечание 3.18. Если в Лемме 3.17 предположить, что Σ не имеет штейнеровских точек в Nr , тогда
достаточно потребовать r < R/2.9 (это будет видно из доказательства Леммы 3.17, Случай 1a).
Теперь Теорема 3.2 доказывается в несколько строчек.
Доказательство Теоремы 3.2. Заметим, что wind(∂T ) = wind(M ) = 2π. Тогда, в силу Леммы 3.17,
каждый глобальный минимайзер Σ состоит из дуг Mr и отрезков касательных к Mr . А значит, имеет
единственную дугу Mr , а ввиду отсутствия петель содержит также конечные компоненты. Конечные
компоненты не могут быть дугами. Следовательно минимайзер является подковой.
4. Доказательства
Ясно, что Σ ⊂ N (N — равномерно выпуклое множество, поэтому в противном случае можно спроецировать часть Σ, лежащуюю в R2 \ N , на N , от чего длина Σ строго уменьшится).
Лемма 4.1. Пусть M выпуклая замкнутая кривая с минимальным радиусом кривизны R > r и
пусть B — шар с радиусом r и центром внутри N . Тогда если B касается M , то B ⊂ N .
В дальнейшем, по умолчанию мы будем полагать M и Σ удовлетворяющими условиям Теоремы 3.2.
Иногда мы будем требовать более слабые условия.
Верно следующее утверждение.
Лемма 4.2. Пусть M — выпуклая замкнутая с минимальным радиусом кривизны R > r и пусть Σ
— произвольный минимайзер для M . Тогда множество EΣ недискретных энергетических точек Σ
лежит на Mr .
Доказательство. Предположим противное. Тогда найдется такая точка x ∈ EΣ \ Mr , что dist (x, M ) <
r − ε для некоторого положительного ε и последовательность {xk } энергетических точек из Bε/2 (x),
сходящаяся к x. Ввиду выпуклости N и того, что минимальный радиус кривизны M не меньше r,
каждая кривая γk := B̄r (xk ) ∩ M связна, так что можно говорить, что каждый xk покрывает дугу γk .
Следовательно, все γj имеют общую точку. Действительно, для точки z ∈ M такой, что dist (x, z) =
dist (z, M ) выполняется
dist (xj , z) ≤ dist (x, z) + dist (xj , x) ≤ r − ε + ε/2 = r − ε/2,
а значит z ∈ γj . Несложно заметить, что тогда либо γi ⊂ γj , либо γi ⊂ γj ∪ γl для некоторых различных
i, j, l. Но тогда одна из точек xi , xj , xl не энергетическая. Противоречие.
Доказательство Леммы 3.5. Доказательство (i): Изменения множества Σ ∩ Nr не влияют на энергию FM (Σ), так что если мы возьмем произвольную связную компоненту S из множества Σ ∩ Nr и
заменим ее деревом Штейнера, соединяющим точки множества S ∩Mr (дерево непусто ввиду связности
Σ и требования FM (Σ) ≤ r, которое влечет Σ \ Nr 6= ∅), тогда длина получившегося множества должна
остаться той же, что была, ввиду оптимальности Σ, а значит компонента S является штейнеровским
деревом, соединяющим S ∩ ∂Nr , как и утверждалось.
Доказательство (ii): Напомним, что Σ = EΣ tXΣ tSΣ , где XΣ — дискретное множество точек, SΣ
состоит из деревьев Штейнера (а значит, из прямолинейных отрезков) и EΣ ⊂ Mr ввиду Леммы 4.2.
Доказательство (iii): Пусть Σ0 произвольная связная компонента множества Σ ∩ Nr . Удалим
произвольный открытый отрезок ∆ ⊂ Σ0 . Значение FM не изменится, то есть FM (Σ0 \ ∆) = FM (Σ),
при этом множество Σ0 \ ∆ разбивается на две связные компоненты Σ1 и Σ2 такие, что Σ0 = Σ1 t Σ2 .
Ясно, что M ⊃ Br (Σ1 ) ∪ Br (Σ2 ). Тогда ввиду связности M существует такая точка A ∈ M , что A ∈
Br (Σ1 )∩Br (Σ2 ), но тогда есть такие точки B ∈ Σ1 и C ∈ Σ2 , что |AB| ≤ r, |AC| ≤ r. Отсюда расстояние
между Σ1 и Σ2 не превосходит |BC| ≤ 2r, а длина удаленного отрезка ∆ не превосходит расстояния
между Σ1 и Σ2 ввиду оптимальности Σ (в противном случае можно соединить Σ1 и Σ2 короче). Пусть
aM (r) максимальное значение |BC| (расстояние между компонентами) по всем допустимым ∆.
В случае если M = ∂BR (O), длина [BC] принимает максимальное значение, когда отрезок [BC]
является хордой и |AB| = |BC| = r. Тогда для этого случая мы можем посчитать максимальное
значение длины [BC]:
|AC|
r
∠AOC
=
=
,
sin
2
2|OC|
2R
9
то есть
∠AOC
∠AOC
cos
|OC| = 2r
|BC| = 2 sin ∠AOC · |OC| = 4 sin
2
2
r
1−
r2
.
4R2
Замечание 4.3. Чтобы доказать Замечание 3.6, мы заменим доказательство Леммы 3.5(iii) следующим,
очень близким, аргументом. Пусть ∆ ⊂ Σ ∩ Nr — произвольный открытый отрезок, а Σ0 снова связная
компонента Σ∩Nr , содержащая ∆. Обозначим за D множество (возможно, пустое) минимальной длины
такое, что (Σ0 \ ∆) ∪ D замкнуто и связно. Ясно, что H1 (D) ≤ 2r: действительно, если Σ0 \ ∆ состоит
из двух связных компонент Σi , i = 1, 2, вспомнив, что Σ покрывает M , мы повторим рассуждения из
доказательства Леммы 3.5(iii) чтобы показать dist (Σ1 , Σ2 ) ≤ 2r, что влечет требуемое утверждение.
Теперь остается только заметить, что
H1 (Σ \ ∆) + 2r ≥ H1 (Σ \ ∆) + H1 (D) ≥ H1 ((Σ \ ∆) ∪ D)
≥ H1 (Σopt ) ≥ H1 (Σ) − a,
и неравенство H1 (∆) ≤ H1 (Σ) − H1 (Σ \ ∆) ≤ 2r + a завершает доказательство Замечания.
Доказательство Леммы 3.7. Предположим противное, т.е. что Σ имеет точку ветвления A0 в Nr .
Ввиду Леммы 4.1 найдется такая точка O ∈ N , что A0 ∈ BR (O) и BR (O) ⊂ N (в частности, BR−r (O) ⊂
Nr ). Обозначим за A одну из точек ветвления Σr , ближайшую к O и положим t := |OA|.
Пусть Σ0 обозначает связную компоненту Σ ∩ Nr , содержащую A. Ввиду структуры локально минимальной сети, найдутся три прямоличейных отрезка Σ0 , начинающиеся в A. Рассмотрим из них такие
два отрезка [AA−1 ], [AA1 ], что точка O принадлежит углу ∠A−1 AA1 (не исключая случай принадлежности стороне угла). Напомним, что угол ∠A−1 AA1 равен 2π/3. Заметим также, что точки A−1 , A1
лежат вне Bt (O). Отсюда один из отрезков [AA1 ], [AA−1 ] пересекает Bt (O). Не умаляя общности будем
считать, что это отрезок [AA1 ]. Обозначим пересечение отрезка [AA1 ] и окружности ∂Bt (O) за C.
Утверждается, что t ≤ aM (r). Предположим противное, тогда поскольку |AC| ≤ aM (r) и |OA| =
|OC| = t > aM (r) ≥ |AC|, имеем ∠OAC > π/3, отсюда отрезок [AA−1 ] также пересекает Bt (O). Обозначим пересечение отрезка [AA−1 ] с окружностью ∂Bt (O) за D и заметим, что угол ∠OAD также больше,
чем π/3, а значит ∠CAD > 2π/3, что противоречит минимальности Σ, завершая доказательство.
Заметим, что точки A1 , A−1 принадлежат Nr , поскольку R − r > 2aM (r) ≥ t + aM (r), и значит
точки A1 , A−1 являются точками ветвления. Также ввиду Леммы 3.5 длины отрезков [AA−1 ] и [AA1 ]
не превосходят aM (r). Рассмотрим правильный шестиугольник P со стороной длины aM (r) такой, что
точка A является его вершиной, а отрезки [AA1 ], [AA−1 ] принадлежат двум его сторонам. Выполняются
следующие утверждения.
• diam P = 2aM (r).
• Отрезок [OA] делит угол ∠A−1 AA1 = 2π/3 на два угла, хотя бы один из которых острый.
Обозначим этот острый угол за ∠OAB, где B — соответствующая вершина шестиугольника P
(то есть |AB| = aM (r)). Тогда угол ∠OBA также острый, поскольку |OA| = t ≤ aM (r) = |AB|.
Поэтому перпендикуляр, опущенный из точки O на прямую (AB), пересекает последнюю на
отрезке [AB], а значит точка O находится внутри квадрата, построенного на стороне [AB]. Но
этот квадрат является подмножеством P , а значит O ∈ P .
• Утверждения выше влекут P ⊂ B2aM (r) (O), и значит P ⊂ Nr .
Возьмем теперь такие вершины A−2 и A2 , что [A1 A2 ], [A−1 A−2 ] ⊂ Σr и точка O принадлежит углам
∠AA1 A2 и ∠AA−1 A−2 . Ясно, что A2 , A−2 ∈ P ⊂ Nr так что они тоже являются точками ветвления. Так же определим и точки A3 , A−3 : [A2 A3 ], [A−2 A−3 ] ∈ Σr и O принадлежит углам ∠A1 A2 A3 и
∠A−1 A−2 A−3 . Точки A3 , A−3 также принадлежат P , а значит и Nr , поэтому тоже являются точками
ветвления. Эти шесть построенных отрезков находятся во внутренности Nr , поэтому не содержат концевых точек. Продолжая последовательно строить эту конструкцию, мы получим два пути в P ⊂ Nr :
один путь (начинающийся с A, A1 , A2 , A3 . . . ) на каждом шаге поварачивает влево, а другой (начинающийся с A, A−1 , A−2 , A−3 . . . ) каждый раз поворачивает вправо. Таким образом, Σ ∩ P ⊂ Σ ∩ Nr
содержит концевую точку, что невозможно в Nr или цикл, что невозможно для дерева Штейнера.
Противоречие.
10
Доказательство Леммы 3.8. Пусть S является связной компонентой множества Σ \ Nr . Сначала мы
докажем, что n(S) ≤ 2. Ввиду свойства (a) множества энергетических точек, для любой энергетической
точки x ∈ S найдется такая точка y = y(x) ∈ M , что |xy| = r и Br (y) ∩ S = ∅. Тогда y может быть
только концом дуги qS , поскольку в противном случае S = S \ Br (y) не связно. Если конец дуги
qS соответствует двум разным энергетическим точкам W1 , W2 множества Σ ∩ S, то qW1 ⊂ qW2 или
qW2 ⊂ qW1 , оба эти случая невозможны, поэтому n(S) ≤ 2, и утверждение доказано.
Докажем теперь, что m(S) ≤ 2. Предположим противное, т.е существование как минимум трех
различных точек входа у S. Обозначим их, против часовой стрелки, соответственно Q1 , Q2 и Q3 . Ввиду
Леммы 3.5 Σr состоит из хорд Mr . Обозначим за W конец хорды Mr в Σr с другим концом в Q2 . Тогда
|Q2 W | ≤ |Q1 W | (в противном случае, заменив в Σ [Q2 W ] на [Q1 W ], получили бы множество лучше),
и аналогично |Q2 W | ≤ |Q3 W |. Заметим, что W ∈
/ S̄, поскольку в Σ нет циклов. Несложно увидеть,
что точки Q1 , Q2 , Q3 , W лежат на Mr в упомянутом порядке против часовой стрелки. В противном
случае дуга qSW является подмножеством qS , где SW — связная компонента Σ \ Nr , содержащая W ,
что невозможно.
Отсюда |W Q2 | составляет хотя бы радиус d максимального шара, вписанного в Nr и касающегося
Q2 .
Поскольку d ≥ 2(R − r), имеем |W Q2 | ≥ R − r > 2r, что противоречит Лемме 3.5(iii), завершая
доказательство.
В заключение заметим, что любое связное подмножество S, содержащее все энергетические точки
S, покрывает qS , и значит, заменив S на дерево Штейнера S̃, соединяющее энергетические точки и
точки входа множества S, мы получим лучшее, чем Σ, множество. Поэтому, ввиду оптимальности Σ,
длины S и S̃ должны быть равны, что доказывает последнее утверждение Леммы.
Замечание 4.4. Поскольку ввиду Леммы 3.8 компонента S является локально минимальной сетью, соединяющей энергетические точки и точки входа, ясно, что энергетические точки являются концевыми
в S. Пусть S содержит две энергетические точки W1 и W2 . Пусть [A1 W1 ] и [A2 W2 ] являются концевыми отрезками S, заканчивающимися в точках W1 , W2 соответственно (не исключая случай A1 = A2 ).
Пусть Qi ∈ qS — такие точки, что Br (Qi ) ∩ Σ = ∅ (ввиду доказательства Леммы 3.8 Qi являются
концами qS ), i = 1, 2. Тогда каждая точка Qi лежит на прямой (Ai Wi ), i = 1, 2.
Доказательство Замечания 4.4. Действительно, S является деревом Штейнера для трех или четырех
точек с A1 , A2 в качестве точек ветвления. Предположим противное, т.е что A1 , W1 , Q1 не лежат на
одной прямой. Тогда можно заменить [A1 W1 ] ∩ Bε (W1 ) с достаточно малым ε > 0 на часть отрезка
[DQ1 ], где D = [A1 W1 ] ∩ ∂Bε (W1 ), получив множество лучше (оно будет иметь длину строго меньше и
несложно видеть, что оно все еще будет покрывать дугу qS ).
˘ ⊂ Σ является дугой Mr .
Доказательство Леммы 3.10. Пусть BC
Заметим, что Σ \ Mr состоит из прямолинейных отрезков: когда Σ является минимайзером, это
следует из Лемм 3.7 и 3.8, а когда Σ является только локальным минимайзером для r < R/5, это
следует из Замечания 3.9.
˘ не содержит точек ветвления. Если Σ является локальным
Заметим, что ввиду Леммы 3.7 дуга BC
минимайзером, то доказательство Замечания 3.9 влечет, что точка ветвления обеспечивает нам отрезок
длины хотя бы 2r + (R − 5r)/4 в Σr .
В остальной части доказательства мы используем только локальные аргументы, так что все дальнейшие рассуждения будут относиться сразу к обоим случаям: когда Σ минимайзер или локальный
минимайзер.
Сначала докажем, что ни B, ни C не совпадает с точкой Sl0 или Sr0 . Предположим противное, то
есть, не умаляя общности, что B = Sr0 . Тогда можно заменить B˘1 B на часть отрезка [B1 A], где B1 =
˘ получим множество лучше Σ (и со строго меньшей длиной). Осталось доказать, что
Bε (B) ∩ BC,
любая дуга в Σ продолжается отрезками касательных к Mr . Сначала докажем, что в Σ дуга не может
продолжаться хордой, затем, что выйти из дуги Mr в “кольцо” N \ Nr можно только в направлении
касательной (что и означает наличие прямолинейного отрезка [BD] ⊂ Σ такого, что D ∈ N \ Nr и,
более того, (BD) касается Mr в B).
11
Qr
Qr
B
H
Ql
E
D
C
B
F
Ql
D
C
O
O
Рис. 4. Случай продолжения хордой. Рисунок к Лемме 3.10.
˘ не может быть продолжена хордой в Σ. Для достаточно малого ε > 0
Мы утверждаем, что BC
˘ F ∈ [BD] такие, что |EB|
˘ = |BF | = ε. Тогда |EB| = ε + o(ε) при ε → 0+ ,
рассмотрим точки E ∈ CB,
поскольку Mr гладкая (условие на кривизну M влечет C 1,1 гладкость). Пусть Qr ∈ M такая точка, что
|Qr B| = r и Br (Qr ) ∩ Σ = ∅, и пусть H является точкой пересечения [EQr ] и ∂Br (Qr ) (как изображено
на Рис. 4). Тогда (BQr ) перпендикулярна касательной прямой к Mr в точке B. Тогда
p
p
|EH| = |EQr | − |Qr H| = |EB|2 + r2 + o(ε) − r = (ε + o(ε))2 + r2 − r
p
= r 1 + o(ε) − r = o(ε).
˘ и отрезком [BF ] меньше π, получаем
Теперь, поскольку угол между дугой EB
p
√ √
|EF | = 2ε2 − 2ε2 cos ∠EBF + o(ε) = 2ε 1 − cos ∠EBF + o(ε) < 2ε − |Ω(ε)|,
и, значит,
˘ + |BF |
|EH| + |EF | < 2ε = |EB|
для достаточно малого ε > 0.
D
Qr
B
Ql
C
O
Рис. 5. Область без точек Σ. Иллюстрация к Лемме 3.10.
Мы утверждаем, что единственный способ войти внутрь кольца N \ Nr из дуги Mr это выйти по
касательной к Mr , то есть если отрезок [BD] ⊂ Σ, тогда D ∈ N \ Nr (как следует из доказанного выше)
и, более того, BD касателен к Mr в B (как изображено на Рис. 5).
12
В противном случае угол между дугой и отрезком будет меньше π и, в достаточно малой окрестности
˘ и отрезок [BF ] ⊂ [BD] на отрезок [EF ],
B, можно, как и в предыдущем случае, заменить дугу EB
уменьшив длину и не увеличив энергию.
Замечание 4.5. Если в постановке Леммы 3.10 M является строго выпуклой кривой, тогда утверждение Леммы 3.10 верно для локальных минимайзеров, т.е. доказательство следует из локальных
аргументов. Также в этом случае Лемма 3.10 верна для R > r.
Доказательство. Действительно, единственная часть в доказательстве Леммы, где мы используем
˘ является дугой Σ ∩ Mr , то C
глобальную минимальность, это доказательство того, что если (BC)
не имеет точек ветвления. Заменим эту часть доказательства Леммы 3.10 следующим аргументом.
Предположим противное, т.е. что есть и хорда [CX] ⊂ Σ ∩ Nr и отрезок [CY ] ⊂ Σ \ Nr . Если M строго
˘ энергетические, и отсюда [CY ] должен быть отрезком
выпуклая кривая, тогда все точки Int(BC)
касательной к Mr в точке C. Но тогда можно поменять Σ так же, как на Рис 4: заменить Σ ∩ Bε (C)
на дерево Штейнера, соединяющее Σ ∩ ∂Bε (C), и пару отрезков длины O(ε2 ) , получив множество,
лучшее чем Σ (и со строго меньшей длиной).
Доказательство Леммы 3.12. Утверждение (ii) доказано в [11]. Чтобы доказать (i), предположим противное, т.е. Int(qS1 ) ∩ Int(qS2 ) 6= ∅ для S1 , S2 , являющихся связными компонентами Σ \ Nr или дугами
Σ ∩ Mr . Очевидно, хотя бы одна из S1 , S2 не является дугой (не умаляя общности, это S1 ). Лемма 3.8
говорит нам, что m(S1 ) ≤ 2. Очевидно, m(S1 ) ≥ 1. Если m(S1 ) = 2 можно отрезать окрестность соответствующей энергетической точки. Длина Σ уменьшится, при этом оно все еще будет покрывать M .
Если m(S1 ) = 1, тогда Лемма 3.10 дает требуемое противоречие.
4.1. Доказательство центральной Леммы.
Доказательство Леммы 3.17. Очевидно, что если S является дугой, то сравниваемые значения равны.
Обозначим за Ql и Qr концы дуги qS . Пусть O является пересечением перпендикуляров к M в
точках Ql и Qr . Заметим, что wind(q) = ∠Ql OQr и обозначим эту величину за γ. Заметим также, что
|QL O| ≥ R, |Qr O| ≥ R. Заметим, что Леммы 3.7 и 3.8 также как и Следствие 3.13 остаются верными
при R > aM (r) + r, что выполняется если R > 5r (или R > 4.98r в том случае, когда M является
окружностью радиуса R), т.е. в условиях доказываемого утверждения.
Надо разобрать следующие случаи.
(1) Пусть S вляется средней компонентой. Тогда она содержит две точки входа и одну или две энергетических точки ввиду Леммы 3.8. Поскольку S является деревом Штейнера для множества
точек входа и энергетических точек, есть четыре возможности для S.
(a) Случай n = 2, m = 2, и существует точка ветвления, смежная с (смежная означает,
что мы воспринимаем S как граф) с обеими точками входа (как изображено на Рис. 6).
Заметим, что если существует точка ветвления смежная с обеими точками входа, тогда есть
и тогда ветвления (обозначим ее за B), смежная с обеми энергетическими точками. Ясно,
что wind(S) составляет π/3. Покажем, что покрываемая дуга qS имеет раствор меньше, чем
π/3. Посчитаем величину дуги, ограниченной продолжениями отрезков, начинающихся из
B. Несложно увидеть, что эта дуга является самой длинной, когда B лежит на Mr (это
предельный случай). А значит, достаточно смотреть на угол в N \ Nr величины 2π/3 с
вершиной B на Mr . Хорошо известно, что дуга является самой длинной в случае, если S
касательна к Mr и когда M является окружностью. В этом случае перпендикуляр к Mr в
точке B разбивает угол ∠Ql BQr = 2π/3 на углы величины π/2 и π/6 (как изображено на
Рис. 7). В этом случае величина дуги составляет
1
π
1
1
+ − arcsin
1−
,
arccos 1 −
α
6
2
α
где α := R/r, а значит она меньше, чем π/3 для α ≥ 2.9.
13
Qr
qS
Ql
2π/3
B
S
γ
O
Рис. 6. Общая ситуация для случая 1a: n = 2, m = 2, есть точка
Штейнера, смежная с обеими точками входа.
D0
qS
Ql
Qr
π/6
π/2
S
B
γ
O
Рис. 7. Предельная ситуация для
случая 1a: n = 2, m = 2, есть точка
Штейнера, смежная с обеими точками входа.
(b) Случай n = 2, m = 2, и нет точки ветвления, смежной с обеими точками входа как
изображено на Рис. 8). Обозначим точки ветвления S за Vl и Vr . В этом случае wind(S) =
π/3 + π/3 = 2π/3. Предположим противное (то есть что γ > 2π/3) и, соединив O с Ql и
Qr , мы получим (невыпуклый) пятиугольник Ql Vl Vr Qr O с двумя углами, равными 4π/3,
и одним углом величины хотя бы 2π/3, что невозможно.
(c) Случай n = 1, m = 2 и существует точка ветвления в S (как изображено на Рис. 9).
Ясно, что wind(S) = π/3. Чтобы доказать утверждение, предположим противное (т.е.
γ ≥ π/3) и, как в предыдущем случае, соединим точку O с точками Ql и Qr . Кроме того,
соединим O с энергетической точкой W , отчего угол величины γ разобьется на две части;
возьмем большую из них (не умаляя общности это ∠W OQr ). Таким образом, у нас есть
треугольник ∆OQr W со стороной |OQr | ≥ R и острым углом (α на Рис. 9) величиной
хотя бы π/6 напротив стороны |W Qr | = r. Вспомнив, что R > 2r и введя обозначение
14
Ql
qS
4π/3
Vl
Vr
O
S
Qr
4π/3
γ
Рис. 8. Рисунок к случаю 1b: n =
2, m = 2, не существует точки
Штейнера, смежной с обеими точками входа.
Qr
qS
r
Ql
W
δ
S
≥R
α ≥ π/6
O
Рис. 9. Рисунок к случаю 1c: m =
2, n = 1.
δ := ∠OW Qr , получим
sin δ =
|OQr |
R
sin α ≥
> 1,
r
2r
что дает нам противоречие.
(d) Последний случай n = 1, m = 2 и нет точки ветвления в S (как изображено на Рис. 10).
Тогда S состоит из двух отрезков [BW ] ∪ [W D], где B, D ∈ Mr , W ∈ XΣ и ∠BW D ≥ 2π/3.
Сначала соединим O с Ql и Qr , затем обозначим Kl = [OQl ] ∩ Mr и Kr = [OQr ] ∩ Mr .
Рассмотрим теперь четырехугольник P , образованный вершинами Kl , Kr , O и W . Сумма
углов Kl , Kr и W в P составляет хотя бы π/2 + ∠BW D + π/2, так что оставшийся угол
(который равен γ) не превосходит π − ∠BW D ≤ π − 2π/3 = π/3, как и утверждалось. В
случае же равенства оба отрезка [BW ] и [W D] касаются M и можно заменить S на дугу
˘ получив множество лучше.
BD,
(2) Пусть S — крайняя компонента (пусть, не умаляя общности, это будет левая крайняя компонента, так что Qr = A). Напомним, что C означает точку ветвления, если S является
треногой, и точку входа, если S — отрезок. Тогда возможны два варианта:
(a) Случай n = 2, m = 1 (как изображено на Рис. 11). Заметим, что S является треногой:
S = [BC] ∪ [CW ] ∪ [CSl0 ] ⊂ (N \ Nr ), где B ∈ Mr . Замечание 4.4 влечет Qr = [CSl0 ) ∩ M ,
Ql = [CW ) ∩ M и |Sl0 Qr | = r = |W Ql |, Br (Qr ) ∩ Σ = Br (Ql ) ∩ Σ = ∅. Пусть K ∈ [OQl )
такая, что (Qr K) ⊥ (OQr ). Тогда α := wind(S) = ∠([BC), [CQr )), ∠([CSl0 ), [Sl0 A)) = 0
и β := ([CQr ), [Qr K)) = ∠([ASl0 ), a). Мы должны показать α + β > γ. Пусть P является
точкой пересечения (KQr ] и [BC). Тогда ∠OKP = π/2−γ и ∠KP C = α+β. Предположим
противное, то есть α + β ≤ γ. Тогда ∠OKP + ∠KP C < π/2, отсюда ∠KLP > π/2, где L —
15
Qr
Ql
W
B
S
D
δ ≥ 2π/3
Kr
Kl
γ
O
Рис. 10. Рисунок к случаю 1d:
m = 2, n = 1 и S состоит из двух
отрезков [BC] ∪ [CD].
ζ = 0◦
K
l
P
π
2
−γ
I
Qr
α+β
β
qS
Ql
Sl0
W C
S
α B
L
Рис. 11. Рисунок к случаю 2a:
крайняя компонента, n = 2, m = 1.
точка пересечения (BC) и (OK), но, поскольку ∠Ql CL = 2π/3, сумма углов в треугольнике
∆CLQl больше π, что невозможно.
(b) Случай n = 1, m = 1 (как изображено на Рис. 12). В случае S = [CSl0 ], где C ∈ Mr ,
γ
|Sl0 Qr | = r, и wind(S) = 0. Обозначим за K такую точку,
что K ∈ [OQl ) и ∠OQr K = π/2.
0
0 O
Определим точки L := [Sl C) ∩ (OQl ) и P := [BSl ) ∩ (Qr K), и введем обозначения α :=
∠P Sl0 Qr и β := ∠Sl0 Qr K.
Имеет смысл рассмотреть следующие две возможности. Заметим, что |Sl0 Ql | = r, в противном случае можно заменить [CSl0 ] ∩ Bε (Sl0 ) на часть отрезка [DQr ], где D = [CSl0 ] ∩ ∂Bε (Sl0 ).
• ∠CSl0 Qr ≤ π (как изображено на Рис. 12). Тогда ∠([ASl0 ), a) = β и ∠([CSl0 ), [Sl0 A)) =
α, так что wind(S)+∠([CSl0 ), [Sl0 A))+∠([ASl0 ), a) = α+β. Заметим, что ∠Sl0 P K = α+β
и ∠OKQr = π/2−γ. Если α+β ≤ γ (что противоречит доказываемому утверждению),
тогда ∠OKP + ∠KP Sl0 < π/2 so ∠KLP > π/2, а это невозможно, поскольку тогда
|CQl | < |Sl0 Ql |, что противоречит |Sl0 Ql | = r, |CQl | ≥ r.
16
H
F
J
K
Ql
π
2
−γ
qS
P
α+β
Qr
Sl0
α
F
θ<
π
2
β
α
S
C
L
K
π
2
−γ
Ql
qS
β
Qr
P
Sl0
κ < π/2
L
C
β−α
α
S
Рис. 12. Рисунок к случаю 2b: крайняя компонента, n = 1, m = 1.
•
γ
O
0
∠CSl Qr >
π (как изображено на Рис. 12). В этом случае ∠([ASl0 ), a) = β и ∠([CSl0 ), [Sl0 A)) =
−α, так что wind(S) + ∠([CSl0 ), [Sl0 A)) + ∠([ASl0 ), a) = β − α и мы знаем, что ∠KP C =
β − α. Если β − α ≤ γ (что противоречит доказываемому утверждению), тогда
∠OKP + ∠KP C < π/2, а это невозможно, поскольку тогда |CQl | < |Sl0 Ql |, что противоречит |Sl0 Ql | = r, |CQl | ≥ r.
Доказательство Следствия 3.4. Пусть Σ является локальным минимайзером в смысле Определения 3.3. Мы покажем, что это так для c := 1/4. Предположим противное, т.е. H1 (Σ) ≤ H1 (Σopt ) +
(R − 5r)/4. Замечание 3.9 показывает, что Леммы 3.7 и 3.8 также как и Следствие 3.13 остаются
верными при r < R/5. Повторяя доказательство Теоремы 3.2 без всяких изменений (мы можем это
сделать, потому что все аргументы, которые использовались в этом доказательстве, также как и в
Лемме 3.17 являются локальными, т.е. на самом деле противоречие возникает с локальной, а не глоγ
бальной, минимальностью Σ),Oмы получаем,
что Σ является подковой.
5. Заключение
Рассматриваемая задача чрезвычайно полезна в народном хозяйстве: она позволит газифицировать
(а также обеспечить водой или иными ресурсами) границы выпуклых областей или регионов. В случае,
если на границе области расположена стена, полученный результат позволит качественно улучшить
условия жизни стражников Стены, а значит сделает более безопасной жизнь во всем регионе.
Список литературы
[1] G. Bouchitté, C. Jimenez, and R. Mahadevan. Asymptotic analysis of a class of optimal location problems. J. Math. Pures
Appl. (9), 95(4):382–419, 2011.
17
[2] A. Brancolini, G. Buttazzo, F. Santambrogio, and E. Stepanov. Long-term planning versus short-term planning in the
asymptotical location problem. ESAIM Control Optim. Calc. Var., 15(3):509–524, 2009.
[3] G. Buttazzo, E. Oudet, and E. Stepanov. Optimal transportation problems with free Dirichlet regions. In Variational
methods for discontinuous structures, volume 51 of Progr. Nonlinear Differential Equations Appl., pages 41–65. Birkhäuser,
Basel, 2002.
[4] G. Buttazzo, A. Pratelli, S. Solimini, and E. Stepanov. Optimal urban networks via mass transportation, volume 1961 of
Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2009.
[5] G. Buttazzo and E. Stepanov. Optimal transportation networks as free Dirichlet regions for the Monge-Kantorovich
problem. Ann. Sc. Norm. Super. Pisa Cl. Sci. (5), 2(4):631–678, 2003.
[6] G. Buttazzo and E. Stepanov. Minimization problems for average distance functionals. Calculus of Variations: Topics from
the Mathematical Heritage of Ennio De Giorgi, D. Pallara (ed.), Quaderni di Matematica, Seconda Università di Napoli,
Caserta, 14:47–83, 2004.
[7] S. Graf and H. Luschgy. Foundations of quantization for probability distributions, volume 1730 of Lecture Notes in
Mathematics. Springer-Verlag, Berlin, 2000.
[8] A. Lemenant. A presentation of the average distance minimizing problem. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat.
Inst. Steklov. (POMI), 390(Teoriya Predstavlenii, Dinamicheskie Sistemy, Kombinatornye Metody. XX):117–146, 308, 2011.
[9] X. Y. Lu and D. Slepcev. Properties of minimizers of average-distance problem via discrete approximation of measures.
SIAM Journal on Mathematical Analysis, 45(5):820 – 836, 2013.
[10] M. Miranda, Jr., E. Paolini, and E. Stepanov. On one-dimensional continua uniformly approximating planar sets. Calc.
Var. Partial Differential Equations, 27(3):287–309, 2006.
[11] E. Paolini and E. Stepanov. Qualitative properties of maximum distance minimizers and average distance minimizers in
Rn . J. Math. Sci. (N. Y.), 122(3):3290–3309, 2004. Problems in mathematical analysis.
[12] A. Suzuki and Z. Drezner. The p-center location problem in an area. Location science, 4(1):69 – 82, 1996.
[13] A. Suzuki and A. Okabe. Using Voronoi diagrams. Drezner, Z. (ed.): Facility location: A survey of applications and
methods, Springer series in operations research, pages 103 – 118, 1995.
E-mail address, Yana Teplitskaya: janejashka@gmail.com
Faculty of Mathematics and Mechanics, St.Petersburg State University, 7/9 Universitetskaya nab., St.
Petersburg, 199034 Russia
18
Отзывы:
Авторизуйтесь, чтобы оставить отзыв