Решение основных задач дискретной геометрии на плоскости - Рышков С.С.

Author: Рышков С.С.

Tags: геометрия теория чисел математика дискретная математика

Year: 2000

Similar

Геометрия на плоскости Теория, задачи, решения

Геометрия дискретных групп

Задачи по геометрии с комментариями и решениями

Сборник задач по дискретной математике

Text

московский
ГОСУДАР( ГГВЕННЫЙ УНИВЕРСИТЕТ
имени М.В.ЛОМОНОСОВА
Механике>- м атом атический факультет
Кафедра Дискретной Математики
С.С.Рышков, Р.Г.Барыкинский, Я.В.Кучериненко
РЕШЕНИЕ ОСНОВНЫХ ЗАДАЧ
ДИСКРЕТНОЙ ГЕОМЕТРИИ
В СЛУЧАЕ ПЛОСКОСТИ
Москва • 2000
ББК 22.135
Р96
УДК 514.174+511.9+519
С.С.Рышков, Р.Г.Барыкинский, Я.В.Кучериненко. Решение ос-
новных задач дискретной геометрии на плоскости.- М.: Изд-во ЦПИ при
механико-математическом факультете МГУ, 2000.- 96 с. Тираж 200 экз.
В этой небольшой, но богато иллюстрированной книге подробно
излагается теория D V-разбиений (разбиений Дирихле-Вороного) и
теория L-разбиений (разбиений Делоне) для евклидовой плоскости.
Также для случая плоскости дана теория параллелоэдров и теория
плотности расположения. Почти для каждой теоремы указано, име-
ет ли она аналог для п-мерного евклидова пространства при и > 2,
и если этот аналог имеется, необходимо ли привлечение новых идей
для его доказательства
В последней главе дана, по-видимому, максимально широкая по-
становка задач об упаковке равных кругов на плоскости и покрытии
плоскости равными кругами. В качестве приложения изложенных
теорий эти две задачи полностью решаются.
Книга предназначена для первого ознакомления с дискретной
геометрией и геометрией положительно определенных квадратич-
ных форм. Изложение вполне доступно для студентов младших
курсов математических специальностей.
Издательство ЦПИ при механико-математическом факультете МГУ.
119899, Москва, Воробьевы горы, МГУ.
Лицензия на издательскую деятельность ЛР 040746 от 12.03.1996 г.
Отпечатано на типографском оборудовании механико-математического
факультета МГУ и Франко-русского центра им. А. М. Ляпунова.
©Коллектив авторов (русский вариант), 2000
Оглавление
Глава 1. Побудительные мотивы, литература и основные
понятия
§1 . Дискретная геометрия и геометрия чисел.....5
§2 . Расположения. Локальная конечность.........8
§3 . Точечные системы. Системы Делоне...........13
Глава 2. L -разбиения и D V-разбиения
§1 . L-разбиение. Пустой круг ("la sphere vide"). Необхо-
димое и достаточное условие ........................16
§2 . D V-разбиение...........................26
§3 . Дуальность £-разбиений и £>V-разбиений .29
Глава 3. Решетки
§1 . Решетки, их основные реперы..............34
§2 . Реперы, решетки и положительно определенные квад-
ратичные формы (ПКФ) .............................40
§3 . Теории приведения. Минимальный вектор. Приведе-
ние по Лагранжу ..................................43
§4 . "Полуоткрытый" параллелограмм решетки.
Леммы Блихфельдта и Минковского...................47
§5 . Характеристические свойства решеток .....51
Глава 4. Параллелоэдры
§1 . Л V-разбиения и £-разбиения решеток .....53
§2 . Перечисление всех параллелоэдров на плоскости . 57
3
§3 . Основные теоремы о параллелоэдрах .......61
§4 . О результатах при п > 2 .................63
Глава 5. Плотность
§1 . Звездные множества. Измерительные фигуры ... 65
§2 . Плотность. Независимость плотности от начала отс-
чета и граничных эффектов .........................70
§3 . Периодические расположения ...............75
§4 . Независимость от измерительной фигуры плотно-
стей плотнейшей упаковки и редчайшего пократия.....78
Глава 6. Упаковки равных шаров. Покрытия равными ша-
рами
§1 . Результаты. Элементарные теоремы ........86
§2 . Плотнейшая упаковка равных кругов........89
§3 . Редчайшее покрытие равными кругами ......92
§4 . О результатах при п > 2 .................94
4
Глава 1
Побудительные мотивы,
литература и основные понятия
§1 Дискретная геометрия и геометрия чисел
1°. Существуют две геометрические дисциплины, имею-
щие достаточно большое пересечение. Мы имеем в виду дис-
кретную геометрию и геометрию чисел. К дискретной гео-
метрии принято относить различные задачи о расположении
точек и фигур в пространстве. К геометрии чисел относятся
те же задачи, но связанные тем или иным образом с точечной
решеткой в n-мерном евклидовом пространстве Еп, а также
некоторые другие задачи о решетке.
Большинство успехов в решении основных проблем дис-
кретной геометрии достигнуто там, где удалось свести их к
задачам геометрии чисел и решить эти задачи.
2°. К основным проблемам дискретной геометрии приня-
то относить:
1) Проблема плотнейших упаковок равных шаров в ев-
клидовом пространстве;
2) Проблема редчайших покрытий равными шарами ев-
клидова пространства;
3) Проблема перечисления всех параллелоэдров.
При перечислении основных проблем дискретной геоме-
трии обычно не упоминают, следующую проблему.
4) Проблема перечисления всех групп движений евкли-
дова пространства, имеющих компактную фундаментальную
область.
Это объясняется тем, что только в случае 4) пробле-
ма дискретной геометрии полностью для любого п (знамени-
тая теорема Шенфлиса-Бибербаха) сведена к проблеме гео-
метрии чисел, а для н < 4 решена методами геометрии чисел
и алгебры.
5
Теорема Шенфлиса- Бибербаха является одной из основ-
ных теорем геометрической кристаллографии. Поскольку
она имеет много хороших подробных изложений при п = 2,
например см. [1]. мы не будем касаться проблемы 4).
К основным проблемам дискретной геометрии, по наше-
му мнению, нужно также отнести еще одну простую пробле-
му, решенную для любого п.
5) Проблема разыскания характеристических свойств,
выделяющих решетки из других точечных систем.
3°. Случай п = 2 отличается от общего случая тем, что
проблемы (1), (2), (3) решаются непосредственно в рамках
дискретной геометрии. Здесь все теории и методы (теория
точечных систем, теория L- и PV-разбиений, теория реше-
ток, теория параллелоэдров и т.д.), сопровождающие реше-
ния упомянутых проблем, гораздо более прозрачны, чем при
п > 2.
4°. В заключение отметим, что предлагаемый текст явля-
ется расширенным изложением семестрового курса лекций,
который читался первым из авторов на механико-матема-
тическом факультете Московского Государственного Универ-
ситета им М.В.Ломоносова. Побудительным мотивом для
прочтения этого курса явились обстоятельства, изложенные
в 3°.
В конце главы 4 и главы 6 дано очень краткое описа-
ние важнейших конкретных результатов в n-мерном случае
по проблемам 3 и 1,2 соответственно.
Таким образом, этот текст можно воспринимать одно-
временно и как "учебник", и как обзор результатов.
При составлении упомянутого курса, использовались, в
частности, следующие книги и статьи, которые авторы реко-
мендуют читателю
[1] Д.Гильберт, С.Кон-Фоссен "Наглядная геометрия" //
М.: Наука, 1981. (D. Hilbert, S. Cohn-Vossen "Anschauliche
Geometric" // Berlin, 1932.)
6
[2] Л.Ф.Тот "Расположения на плоскости на сфере и в
пространстве" // М.: Физ.-Мат.ГИЗ (L. Fejes Toth "Lagerun-
gen in der Ebene auf der Kugel und im Raum" // Springer-Verlag,
Berlin • Gottingen • Heidelberg, 1953.)
[3] Б.Н.Делоне "Геометрия положительных квадратич-
ных форм" // Успехи Мат. Наук, Вып. 3, (1937), с. 16-62;
Вып. 4, (1938), с. 102-164.
[4] С.С.Рышков "Теория точечных решеток" // (Готовит-
ся к печати.)
[5] Р.М.Gruber, (.'.G.Lekkerkerker "Geometry of numbers" //
North-Holland Math. Library, V. 37. North-Holland, Amsterdam
• New York • Oxford • Tokyo.
Заметим, что предлагаемый текст является несколько
пополненным русским вариантом статьи в книге "Теория чи-
сел", готовящейся к изданию в Индийском Книжном Агенст-
ве. Все замеченные нами в рукописи, поданной в ИКА, неточ-
ности и опечатки здесь нами исправлены.
5°. После номеров теорем мы иногда будем указывать:
п.п- аналогичная теорема верна при любом п, приведен-
ное доказательство также распространяется на любое п,
п.2 - аналогичная теорема верна при любом п, но приве-
денное доказательство не распространяется на любое п,
2.2 - теорема верна лишь при п = 2.
Мы систематически используем следующие обозначения:
t> - начало доказательства
• - конец доказательства
>• - доказательство очевидно.
6°. Мы очень благодарны всем математикам, на чьих ре-
зультатах базируется этот курс.
Авторы глубоко благодарны М.Д.Ковалеву и З.Д.Ломаки-
ной, прочитавшим рукопись и давшим много полезных сове-
тов и замечаний.
Первый из авторов поддержан Российским Фондом Фун-
даментальных Исследований, грант №97-01-00266.
7
§2 Расположения. Локальная конечность
1°. Во всей статье Е2 обозначает евклидову плоскость с
ортонормированной системой координат (О, £1,^2), началом
которой служит некоторая фиксированная точка О G Е2.
Под словом "фигура " всюду в статье понимается ограни-
ченное подмножество плоскости, измеримое по Жордану. В
дальнейшем, говоря о площади подмножества плоскости, мы
будем подразумевать, что оно измеримо по Жордану и эта
площадь равна его Жордановой мере.
Под словами "выпуклое множество" понимается вы-
пуклое множество плоскости, содержащее по крайней мере
одну внутреннюю точку.
Рангом не пустого множества мы будем называть раз-
мерность его линейной оболочки.
Определение. Произвольная счетная система Т = {Т].
Т2, ..} множеств 7], Тг,. •. плоскости Е2 называется располо-
жением (этих множеств).
Вообще говоря, некоторые из элементов (множеств) рас-
положения или даже все они могут быть попарно конгруент-
ны, некоторые могут пресекаться или, например, совпадать
друг с другом.
В дальнейшем мы, обычно особо этого не оговаривая, бу-
дем рассматривать расположения ограниченных множеств.
Одним из примеров расположения является произволь-
ная (счетная) точечная система 27 (см. ниже), т.е. в качестве
элементов расположения могут выступать и точки.
Расположение множеств, при котором никакие два из них
не пересекаются (то есть, если Т} П Tj = 0, для i,j = 1,2,...
и i 0 7), называется строгой (дизъюнктной) упаковкой
(этих множеств).
Расположение Т = СТг, • - •}> ПРИ котором Е2 = U^*-
называется покрытием плоскости Е2 (этими множествами).
Расположение Т = {71,7г,---}, являющееся как покры-
тием, так и строгой упаковкой, называется точным (дизъ-
8
юнкнтным) разбиением плоскости Е2.
Расположение Т = {71, Тг,..в котором никакие два эле-
мента не пересекаются по внутренним точкам (т. е., если
int7} П intTy = 0, для i, j = 1,2,... и i / J), называется (клас-
сической) упаковкой (этих множеств).
Расположение Т = {ТьТг, •••} замкнутых множеств, яв-
ляющееся как покрытием, так и (классической) упаковкой, на-
зывается (классическим) разбиением плоскости Е2.
При рассмотрении классического разбиения мы в даль-
нейшем особо подчеркивать, что все его элементы - замкну-
тые множества, не будем.
Далее, если будет ясно, о разбиениях или упаковках какого
вида идет речь: точных или классических, или если высказы-
вание будет справедливо и для тех и для других, мы будем ис-
пользовать только слово "разбиение" или "упаковка". Кроме
того, мы, естественно, не будем оговаривать, что рассматри-
ваем разбиения (всей) плоскости.
Определение. Расположение I С Е2 называется пра-
вильным, если существует группа движений плоскости, ко-
торая транзитивно действует на этом расположении.
(Всюду здесь под словом "движение" мы понимаем дви-
жение как первого, так и второго рода.)
Определение. Расположение I С Е2 мы будем называть
тпрансляционно правильным, если существует такая груп-
па параллельных переносов плоскости, которая транзитивно
действует на этом расположении.
В качестве примера, можно рассмотреть"бесконечный"
лист клетчатой бумаги. Семейство замкнутых квадратиков
этого листа образует правильное классическое покрытие, а
семейство открытых квадратиков образует правильную упа-
ковку. Семейства. ребер - сторон квадратиков, и узлов - их
вершин, являются правильными расположениями. Располо-
жения квадратиков и р<Й>ер трансляпионно правильны. В то
же время, расположение ребер правильно, но не трансляцион-
9
но правильно, так как группа, транзитивно действующая на
этом расположении, содержит поворот на 90°.
2°. Расположение Т = ...} называется локально
конечным, если любая точка A G Е2 имеет окрестность, пе-
ресекающую лишь конечное число элементов (множеств) рас-
положения X
Лемма 1, п.п. Для того, чтобы расположение Т было
локально конечным, необходимо и достаточно, чтобы любое
ограниченное множество М С Е2 имело непустое пересечение
лишь с конечным числом элементов расположения Т.
> Достаточность тривиальна. Докажем необходимость.
Пусть задано ограниченное множество М. Если его замыка-
ние. пересекается лишь с конечным числом элементов рас-
Рис. 1.01
положения X то и оно само
пересекается лишь с конеч-
ным числом элементов рас-
положения X Поэтому мы
можем считать множество
М замкнутым. Построим
вокруг каждой точки мно-
жества М окрестность, име-
ющую непустое пересечение
лишь с конечным числом
элементов расположения X
Полученная система ок-
рестностей индуцирует от-
крытое покрытие компакта
М. Из этого покрытия выбираем конечное подпокрытие. Оче-
видно, что множество М пересекается лишь с частью из тех
элементов расположения X с которыми пересекается объеди-
нение всех элементов построенного подпокрытия.»
Если читателю неизвестна использованная в доказатель-
стве топологическая теорема, он может заключить множест-
во М в достаточно большой квадрат и взять окрестности
10
точек множества М гомотетичными этому квадрату. Далее
для достижения цели читатель может использовать несколько
раз лемму Гейне-Бореля.
Лемма 2, п.п. Пусть для некоторой упаковки Т сущест-
вуют такие числа г > 0 и R > 0, что для любого множества
Ti € Т найдутся замкнутый объемлющий круг радиуса R и
вложенный открытый круг радиуса г, тогда упаковка Т ло-
кально конечна.
t> Возьмем произвольную точку А G Е2 и t > 0 и опишем
вокруг точки А круги U и V радиусов с и 2R + с. Каждое
множество Т{ Е Т, для которого ТгП(/ 0, содержится в круге
V вместе со своими кругами радиуса R и г (см. рис. 1.01).
Но вписанные в множества 7} G Т круги радиуса г попарно не
пересекаются. Поэтому в круге V их, очевидно, не более, чем
((2Л + е)/г)2..
3°. Теорема 1.1, п.п. Каждое локально конечное разби-
ение плоскости на ограниченные выпуклые множества явля-
ется ее разбиением на выпуклые многоугольники.
t> В силу
выпуклости
множеств
разбиения
следует, что
для любых
двух мно-
жеств, имею-
щих в пересе-
чении не ме-
нее одной точ-
ки, существу-
ет прямая, Рис. 1-02
содержащая
их пересечение (см. рис. 1.02). То есть каждые два эле-
мента разбиения либо не пересекаются, либо имеют общую
точку, либо имеют общий отрезок. Из локальной конечности
получаем, что каждое множество разбиения пересекается с
конечным числом других множеств.*
Сейчас мы введем несколько понятий, которые нам в рав-
ной мере потребуются в дальнейшем. Для удобства мы да-
дим формулировку этих понятий и в случае расположений в
/?.-мерном евклидовом пространстве.
Как обычно, при рассмотрении выпуклого 71-мерного
многогранника мы будем называть его вершины 0-мерными
гранями, ребра - 1-мерными гранями и т.д., сам многогран-
ник - ?1-мерной гранью. Стенками выпуклого 7?.-мерного
многогранника мы будем называть его п — 1-мерные грани.
Классическая упаковка выпуклых многогранников (мно-
гоугольников), в которой каждые два многогранника (много-
угольника) либо не пересекаются, либо имеют общую целую
грань того или иного измерения (либо общую вершину, либо
общее ребро), называется нормальной или грань-в-грань
упаковкой.
Нормальное (грань-в-грань) разбиение - это такое клас-
сическое разбиение., которое является классической грань-в-
грань упаковкой.
Для грань-в-грань разбиений на выпуклые многогранники
(многоугольники) естественно вводится понятие грани разби-
ения, как грани любого из многогранников (многоугольников)
разбиения.
Классическое разбиение на выпуклые многогранники
(многоугольники) называется стенка-в-стенку * 2) (ребро-в-
ребро) разбиением, если для каждых двух многогранников
(многоугольников) разбиения, имеющих в пересечении вну-
треннюю точку стенки (ребра) одного из них, эта стенка (это
ребро) является стенкой (ребром), как одного так и другого
face-to-face.
2) facet-to-facet.
12
многогранника (многоугольника).
Лемма 3, п.2. Локально конечное разбиение на выпук-
лые многогранники (многоугольники) тогда и только тогда
является грань-в-грань разбиением, когда оно является стен-
ка-в-стенку (ребро-в-ребро) разбиением. >•
Нормальное разбиение п-мерного евклидова пространст-
ва на выпуклые многогранники называется примитивным,
если в каждой его вершине сходится n + 1 его элементов.
§3 Точечные системы. Системы Делоне
1°. Точечной системой S С Е2 мы будем называть про-
извольное счетное множество точек плоскости Е2 (произволь-
ное расположение одноточечных множеств).
Определение.
Точечная система
S С Е2 называется
< 1,0 > - сисп 1емо й,
если для некоторого
г > 0 она обладает
следующим "г-свойс-
твом": в каждом
открытом круге
U С Е2, имеющем
радиус г, найдется
не более одной точ-
ки, принадлежащей
системе Е (см. рис. 1.03). Верхняя грань множества таких
чисел г будет обозначаться через г^.
Очевидно, что каждая <1,0 >-система локально конечна,
т.е. является локально конечным расположением одноточеч-
ных множеств.
Определение. Точечная система S С Е2 называется
< 0,1 >-системой, если для некоторого R > 0 она облада-
ет следующим "Я-свойством": в каждом замкнутом круге
R
Рис. 1.03
13
U С Е2, имеющем радиус R, найдется по крайней мере
одна точка, принадлежащая системе Е (см. рис. 1.03 ).
Нижняя грань множества таких чисел R будет обозначаться
через Rs-
Определение. Точечная система Г С Е2 называется
< 1,1 >-системой или системой Делоне, если она одно-
временно является и < 1,0 >-системой и < 0,1 >-системой
(см. рис. 1.03).
• • • • 4 а • • • 3 а а а • 2 * * 1 У • • • а • а а а • а а а а а а • • • • •
• а а а • • • а • • • • *. 2 . 3 . * . s .х а а а а а а а а а а
. . . .
Рис. 1.04
Лемма 4, п.п. Аффинный образ любой <1,1 >-систе-
мы (< 1,0 >-, < 0, 1 >- системы) есть снова <1,1 >-система
(< 1,0 >-, < 0, 1 >-система). с>«
Обычно (с заменой в определении <1,1 >-системы ра-
диуса г на г/2) < 1,1 >-систему называют {г, /?)-системой
или равномерно дискретной системой. Иногда < 1,1 >-
систему называют (г, Н)-системой, имея ввиду, что она обла-
дает /’-свойством и Я-свойством именно для заданных число-
вых значений г > 0 и R > 0. Величины rs,Rs называются
основными константами системы Е.
14
Лемма 5, п.п. Каждая (г,К)-система Е является
(гр, Rs)-системой, но не является (г', R' J-системой ни при ка-
ких г' > rs и (или) R' < Rs- <>•
Примеры. Зададим на декартовой плоскости хОу три
системы I], Т2, ‘Хз точек вида (х,,т/,), где х, = 5\, yj = 5) :
i,j 6 Z. Пусть, во-первых, 5’(J = 0,5) = S'i-i + г, 5'_г- = —5', при
г = 1,2,... (см. рис. 1.04). Очевидно, что полученная система
1] является <1,0 >-системой (для любого г < л/2/2), но не
является < 0,1 >-системой.
:::::::::::: : : : : *у : : : : :
........... • ± ........................................—
........................ ii : : ...................
*1 ...............
।
1 !
I
........... ‘ “ 4 Ч Hi'..............*
i
Рис. 1.05
Пусть, во-вторых, 5'o = 0,5) = 5)-i+ l/г , 5’_,- = —5) при
г = 1,2,... (см. рис. 1.05). В этом случае точечная систе-
ма Т2 (ее локальная конечность следует из расходимости га-
рмонического ряда) является < 0,1 >-системой (для любого
R > л/2/2), но не является <1,0 >-системой.
Пусть система совпадает с системой Т] в правой полу-
плоскости и с системой Т2 в левой. Тогда, как легко видеть,
система не является ни < 0. 1 >-, ни < 1,0 >-системой.
15
Глава 2
L-разбиения и /ж-разбиения
§1 L-разбиение. Пустой круг ("la sphere vide").
Необходимое и достаточное условие
1°. Пусть задана <1,1 >-система S С Е2.
Определение. Каждая выпуклая фигура L С Е2 назы-
вается L-фигурой <1,1 >-системы S С Е2, если она являет-
ся выпуклой оболочкой множества 27' С Г, удовлетворяющего
следующим условиям:
1) S' С £°, где L° некоторая окружность.
2) Множество S' полностью определяет окружность L0.
3) L* П S — S', где L* - круг, ограниченный окружностью
L°, т.е. внутренность круга L* пуста от точек системы S.
Окружность L0 называется L-окружностью системы S,
а круг L* называется L-кругом системы S. Через {£}д,
{L0}£ и {L*}е далее обозначаются, соответственно, множест-
ва всех L-фигур, L-окружностей и L-кругов системы S. (Ом.
рис. 2.01.)
Лемма 1, п.п. Каждая L-фигура, отвечающая произ-
вольной <1,1 >-системе. есть выпуклый ограниченный мно-
гоугольник.
о Множество S' конечно как ограниченное подмножество
<1,1 >-системы. Так как множество S' полностью определя-
ет окружность и, тем самым, имеет ранг 2, лемма доказана.*
Лемма 2, п.п. ("Пустой круг.") Каждой <1,1 >-систе-
ме отвечает по крайней мере один L-многоугольник.
с> Пусть задана <1,1 >-система S С Е2. Рассмотрим "1а
sphere vide", т.е. круг, не содержащий ни внутри, ни на гра-
нице точек системы S (см. рис. 2.01). Будем каким-нибудь
способом непрерывно передвигать этот круг, одновременно
непрерывно и априори неограниченно увеличивая его радиус.
В некоторый момент наш круг встретится, вообще говоря, с
16
одной из точек системы Е, скажем с точкой А. После этого
мы будем так двигать наш круг, не переставая увеличивать
его радиус, чтобы точка А оставалась на его границе. В неко-
торый момент наш круг встретит еще одну из точек системы
Рис. 2.01
Е, скажем точку В. Затем будем продолжать увеличивать
радиус круга так, чтобы точки А и В оставались на границе
круга. В некоторый момент наш круг встретит еще одну из
точек системы Е, скажем точку С. Каждая из упомянутых
точек существует в силу того, что круг радиуса Ад должен
содержать точки системы Е. Таким образом, на поверхности
круга оказалась совокупность точек, полностью его определя-
ющая, т.е. движение нашего пустого круга и увеличение его
радиуса становится невозможным. Полученный круг, очевид-
но, является L-кругом, отвечающим системе Е, а выпуклое
замыкание множества точек системы Е, лежащих на его гра-
нице, является A-фигурой, отвечающей системе Е.•
17
Лемма 3, п.п. Для каждой < 1,1 >-системы Е множе-
ства {L}e, {L0}^ и {L*}e счетны. То есть все эти множества
являются расположениями. t>«
2°. Теорема 2.1, п.п. Совокупность всех L-мно-
гоугольников произвольной <1,1 >-системы ГС Е2 есть ло-
кально конечное нормальное разбиение плоскости.
с> Пусть задана <1,1 >-система Е и построены все опре-
деляемые ею L-многоугольники. Разобьем доказательство на
несколько частей.
1) Заметим, что каждое ограниченное множество пере-
секается лишь с конечным числом L-многоугольников. Дей-
ствительно, пусть М С Е2 - такое множество, d - его диа-
метр и А € М. Точка А может принадлежать только тем
L-многоугольникам, вершины которых отстоят от нее не бо-
лее, чем на 2R г, таким образом диаметр множества вершин
тех L-многоугольников, которым могут принадлежать точки
множества М, не превосходит d + Конечность числа
L-многоугольников с таким набором вершин очевидна.
2) Покажем, что множество {L}e есть нормальная упа-
ковка.
Действительно, пусть два различных L-многоугольника
18
L] и L2 имеют общие точки. Отсюда сразу следует, что со-
ответствующие им L-круги L\ и L2 различны, но пересече-
ние их не пусто. Случай касания кругов L*, L*2 тривиален.
Рассмотрим прямую Р, содержащую общую хорду этих кру-
гов. Прямая Р делит каждый из кругов L\ и L2 на две части
- "шапочки", обе. шапочки каждого круга нам будет удобно
считать замкнутыми. Из двух шапочек круга L\ одна лежит
полностью в круге L2 - ее мы будем называть внутренней,
другую внешней (по отношению к кругу L2}. Соответствен-
ные названия мы дадим и шапочкам круга L2. Очевидно, что
точки системы 27, за исключением вершин многоугольников
Li и L2, могут быть расположены лишь вне объединения кру-
гов L* U L2 - такие точки нам сейчас не нужны (рис. 2.02).
Вершины многоугольника Li (L2) лежат на границе внешней
шапочки круга L* (L^). Отсюда следует, что пересечение
Lj П L2 лежит в пересечении внешних шапочек, т.е. много-
угольники L] и L-i соприкасаются либо по вершине, либо по
ребру.
3) Рассмотрим теперь любой многоугольник L\ С {L}r-
19
и одну из его сторон F. Рассмотрим также прямую Р, содер-
жащую сторону F. Центр О круга L\ лежит на перпендику-
ляре к прямой Р в точке О' - середине стороны F. Прямая
Р разбивает круг L* на две шапочки (см. выше), одна из ко-
торых содержит точки системы 27 только в концах ребра F
- точках Ап В пересечения L\ с прямой Р. Рассмотрим на
прямой ОСУ точку Ot на расстоянии t от точки О в сторону
пустой шапочки (см. рис. 2.03). Далее, построим круг Ut с
центром в точке Ot, пересекающий прямую Р в точках А и
В.
При малых t круг Ut содержит только точки Аи В си-
стемы 27. При больших значениях t в круге Ut содержатся
и новые точки из системы 27, обозначим через t! наимень-
шее из таких t. Очевидно, что круг Ut< содержит новые точ-
ки лишь на границе. Отсюда вытекает, что круг Uf есть L-
круг, а стороной F и новыми точками определен некоторый
Д-многоугольник Дг € {Д}д, смежный с многоугольником L}
по стороне F. Итак, для любого /^-многоугольника мы наш-
ли другой Д-многоугольник, смежный с исходным по наперед
заданной его стороне.
4). Нам осталось показать, что каждая точка A G Е2
лежит по крайней мере в одном многоугольнике из множества
{Mr-
Рассмотрим произвольную точку A G Е2, произвольный
многоугольник Д € Дд, точку О GintL и отрезок [О, А]. В си-
лу локальной конечности расположения Дд отрезок [О, А] пе-
ресекается с конечным числом Д-многоугольников (см. рис.
2.04). Без уменьшения общности, точку О Gint Д считаем вы-
бранной таким образом, что {полуинтервал [О, А) пересекает
указанные Д-многоугольники только по внутренним их точ-
кам и внутренним точкам их ребер} Тогда, применяя ко-
Заключенный в фигурные скобки текст - это двумерный
вариант так называемой Леммы о шашлыке, п.п.
20
нечное число раз результат пункта 3), можно найти L-много-
угольник, содержащий точку А.»
Пусть 17 С Е2 - произвольная <1,1 >-система. Доказан-
ная теорема позволяет ввести следующее:
Определение. Разбиение называется L-разбиени-
ем или разбиением Делоне, отвечающим < 1,1 >-системе
£ (для 17) (см. рис. 2.01).
Следствие: (из теоремы 1.2.) Для любой < 1,1 >-
системы 17 разбиение единственно. с>«
Отметим, что звезда любой вершины разбиения {L}^,
т.е. множество всех его многоугольников, инцидентных этой
вершине, для любой < 1,1 >-системы конечна. Это следу-
ет из локальной конечности L-разбиений для таких систем.
(Звезда любого ребра разбиения {L}^, т.е. множество всех
его многоугольников, инцидентных этому ребру, состоит из
двух многоугольников.)
Отметим еще одно простое, но важное утверждение.
Теорема 2.2. Пусть данная < 1,1 >-система переводит-
ся в себя некоторым движением, тогда этим же движением
переводится в себя и отвечающее ей L-разбиение. о*
3°. L-разбиение. (Необходимый и достаточный
признак.) Пусть заданы некоторая <1.1 >-система 17 С Е2
и локально конечное нормальное разбиение X плоскости Е2 на
21
выпуклые многоугольники.
Будем говори ть, что разбиение Т совместимо с < 1,1 >-
системой 27, если каждая точка системы 27 есть вершина раз-
биения Т, а каждая вершина разбиения Т есть точка системы
27.
Теорема 2.3, п.п. Г’азбиение Ч, совместимое с некото-
рой < 1,1 > -системой 27, является L-разбиением, отвечаю-
щим этой системе, тогда и только тогда, когда:
1) Каждый многоугольник разбиения Т можно вписать в
круг.
2) Для любой пары многоугольников разбиения Т, сме-
жных по ребру, каждая вершина одного из этих многоуголь-
ников, не принадлежащая указанному ребру, лежит вне круга,
описанного вокруг другого многоугольника данной пары.
t> Необходимость указанных условий непосредственно сле-
дует из определения.
Докажем достаточность. Пусть Ту - произвольный мно-
гоугольник разбиения Т и Т* - описанный вокруг него круг.
Очевидно, что для доказательства теоремы достаточно дока-
зать пустоту круга Т* от точек системы 27, не являющихся
вершинами многоугольника Ту.
Рассмотрим произвольную точку >4 G 27, не являющуюся
вершиной многоугольника Ту.
Так выберем точку О GintZi, чтобы полуинтервал [О, А)
не проходил через вершины многоугольников разбиения Т.
Будем для удобства описания считать, что отрезок [О, Л] го-
ризонтален и что последовательность многоугольников, пе-
ресекающиеся с полуинтервалом [О,>4), идет слева направо.
Пусть зти многоугольники занумерованы в последователь-
ность ... ,Тт так, что A G Тт. Обозначим через Т*,
где i = l,2,...,m, круг, описанный вокруг многоугольника
Д, а через 73,-, где j = 1,2, ...,m — 1, прямую, содержащую
пересечение 7} Я 7}+j (см. рис. 2.05).
Из построения отрезка [О, Д] следует, что точка А лежит
22
правее всех прямых Р,. Рассмотрим многоугольники Trn~i и
Тт. В силу условия 2) точка А не принадлежит кругу 7Д_].
Внутренняя шапочка круга ТД_2 относительно круга 7Д_1 со-
держится внутри ТД_1 и значит не содержит точку А. А так
как точка А лежит правее прямой Рт_2, она не содержит-
ся и в круге Т*п_2 (см. рис. 2.05). Проведя последователь-
но такое рассуждение и для остальных многоугольников 7},
i = m — 3, m — 4,..., 1, получим, что точка А лежит вне круга
Г]*. Таким образом, каков бы ни был задан многоугольник
Т\ G Т, никакая точка A G X1, не являющаяся его вершиной,
не может лежать ни внутри, ни на границе круга ТД*
4°. Пример 1. Рассмотрим разбиение Тд на правильные
треугольники со стороной а. Рассмотрим систему состо-
ящую из вершин разбиения Тд, и систему состоящую из
центров тяжести треугольников разбиения Хд (см. рис. 2.06).
Очевидно, что L-разбиением для системы является разби-
ение T/j. Найдите L-разбиение для системы Е2.
Пример 2. Рассмотрим систему X1, состоящую из точек
решетки Z2 и всех точек вида (т, у) — (А:+ 1/4, Z + 1/2), где к и I
- целые числа. Система X? есть <1,1 >-система с основными
константами rv = уТ0/4 и Rr — 5/8.
23
Рассмотрим треугольники (см. рис. 2.07):
7*1 = {(—3/4,1/2), (0,1), (1/4,1/2)},
Т2 = {(—3/4,1/2), (0,0), (1/4,1/2)},
Тз = {(0,0), (1,0), (1/4,1/2)}, Ть = {(0,1), (1,1), (1/4,1/2)}.
Легко видеть , что множество Т всех треугольников, каж-
дый из которых параллельно конгруэнтен одному из постро-
енных четырех, образует нормальное разбиение плоскости,
совместимое с системой S.
Рис. 2.06
Проверим, что разбиение Т есть L-разбиение, отвечающее
системе 27. Первое условие достаточного признака выполнено
тривиально. Для проверки второго выпишем уравнения ок-
ружностей, описанных вокруг наших четырех треугольников:
= {(% + 1/4)2 + (У - 9/16)2 = 65/256},
= {(X + 1/4)2 + (У - 7/16)2 = 65/256},
7з = {(X — 1/2)2 + (У — 1/16)2 = 65/256},
Т° = {(X - 1/2)2 + (У - 15/16)2 = 65/256}.
24
Вершины треугольников смежных с исследуемыми име-
ют, соответственно, координаты:
Ту : {(-1,1), (1,1), (0,0)}, Т2 : {(-1,0), (0,1), (1,0)},
Т3 : {(-3/4,1/2), (5/4,1/2), (1/4, -1/2)},
Т4 : {(-3/4,1/2), (5/4,1/2), (1/4,3/2)}.
Подставляя эти координаты, в уравнения окружностей
Т°, Т2, Т3 и 7g, убеждаемся в том, что условие 2) выполнено
и разбиение Т есть L-разбиение.
Рис. 2.07
5°.(п.п.) (.'одержание этого пункта нигде в дальнейшем
не используется, поэтому приведенные в нем теоремы не до-
казываются.
Зададим число е > 0. Тогда <1,1 >-система S' называ-
ется е-близкой к системе S, если точки системы S' можно
занумеровать таким способом, что для любого натурально-
го числа i выполнено неравенство р(А,И;) < е, где A, G S и
25
A' G Д'.
Теорема 2.4 Для произвольной < 1,1 >-системы Д и
любого числа t > 0 найдется такая (.-близкая к ней < 1,1 >-
система Д', что разбиение L? симплициально.
Теорема 2.5 Для произвольной такой системы Делоне
Д, что разбиение симплициально, и любого компактно-
го множества F С Е2 найдется такое число е > 0, что любая
е-близкая к системе Д система Делоне Д', отличающаяся от
системы Д лишь на (-окрестности компакта F, имеет сим-
плициальное L-разбиение.
Мы рекомендуем читателю самому попробовать доказать
эти две теоремы, а также построить пример такой системы
Делоне Д с симплициальным разбиением L^, что для любого
числа е > 0 найдется е-близкая к ней система Делоне Д', для
которой L-разбиение уже не симплициально.
§2. £>У-разбиение
1°. Определение. Пусть задана <1,1 >-система Д С
Е2. Областью Дирихле-Вороного (DV-областью) с цен-
тром в точке A G Д относительно системы Д называется
множество DV& таких точек X G Е2, что р(А,Х) < р(В,Х)
для любой точки В G Д.
Множество всех DV-областей относительно системы Д с
центрами во всех точках системы Д, мы будем обозначать
через {Д>У}г (см. рис. 2.08).
Теорема 2.6, п.п. Для любой <1,1 >-системы (систе-
мы Делоне) Д С Е2 и любой точки A G Д область ВУд есть
замкнутый многоугольник, диаметр и число граней которо-
го не превосходят величин зависящих от основных констант
системы Д.
t> Пусть задана <1,1 >-система Д и точка А € Д. Ника-
кая точка X € Е2, удаленная от точки А более, чем на не
может принадлежать множеству DVa, поскольку в ее круго-
вой окрестности радиуса В % найдеся точка В G Д, очевидно,
26
отличная от точки А.
Далее, область DVa есть пересечение замкнутых полупло-
скостей, ограниченных прямыми, перпеникулярными к сере-
динам отрезков вида [А, В], где В G Е \ {А} (см. рис. 2.08).
Обратим внимание на то, что полуплоскости, для которых
[А, В] > 2Re, в образовании области DVa принимать участия
не могут, так как дополнения этих полуплоскостей отстоят от
области DVa на положительное расстояние. Таким образом, в
образовании области DVa может принимать участие не более
чем [(2/?£ + гs)/ге\2 полуплоскостей. См. доказательство
леммы 2 главы !.•
Теорема 2.7. Для любого выпуклого многоугольника
М С Е2 найдется такая <1,1 > -система Е, что М G {DV}r.
t> Выберем произвольную точку A GintM и отразим ее
во всех ребрах многоугольника М. Пусть А' - одна из таких
отраженных точек, F - соответствующее ребро и V - несу-
щая прямая этого ребра. Все точки пространства Е2, которые
27
ближе к точке А, чем к точке Д', образуют вместе с прямой
Р одну из полуплоскостей, определяющих многоугольник М.
Таким образом, точка А и все ее зеркальные образы дают
< 1,0 >-систему, для которой многоугольник М удовлетво-
ряет всем условиям определения области DVa-
Построим теперь нужную нам < 1,1 >-систему. Пусть
диаметр многоугольника М равен d. Возьмем произвольную
<1,1 >-систему, выкинем из нее все точки, попавшие в круг
радиуса 3d с центром в А и добавим вместо них построенную
выше <1,0 >-систему.*
Теорема 2.8, п.п. Совокупность {DV}^ всех DV-облас-
тей произвольной <1,1 >-системы 2J есть локально конечное
нормальное разбиение плоскости Е2. (Это разбиение называ-
ется разбиением Дирихле-Вороного или DV-разбиением.)
о То, что совокупность {DV} g есть классическое разбие-
ние, очевидно. Также очевидно, что любое ограниченное мно-
жество пересекает лишь конечное число .DV-областей систе-
мы 27.
Пусть теперь для некоторой <1,1 >-системы 27 разби-
ение {DV}j; не нормально и следовательно не ребро-в-ребро.
Тогда найдется такая область DVa С. {DV}r и такое ее ребро
F, что по внутренним точкам ребра F к области DVa при-
лежит , по крайней мере, две, скажем DVq и DVc, различ-
ных DV-области. Но тогда отрезки [А, В] и [А, С*], не являясь
отрезками одной и той же прямой, одновременно перпенди-
кулярны прямой, содержащей ребро F, что невозможно.*
Отметим, что звезда любой вершины и любого ребра раз-
биения {DV}r для любой <1,1 >-системы конечна (см. рис.
2.08). Это следует из локальной конечности DV-разбиений
для таких систем.
Теорема 2.9, п.п. Пусть данная < 1,1 >-система пе-
реводится в себя некоторым движением, тогда этим же дви-
жением переводится в себя и отвечающее ей DV-разбиение.
о*
28
2°. Пример 1. Рассмотрим разбиение (см. рис.
2.06), а также системы Б] и Г2. (См. §2, пункт 4.) Очевидно,
что UV-разбиением для системы Г2 является разбиение
Найдите L-разбиение для системы Б].
Пример 2. Рассмотрим систему Делоне Б, построен-
ную в пункте 3, §2 (см. рис. 2.07). Здесь есть DV-области
двух и только двух видов: с целыми и с дробными центрами.
Построим эти области.
Область DV(0(j) имеет вершины (—1/4,7/16), (1/2,1/16),
(1/2, -1/16), (—1/4, -7/16), (-1/2, -1/16), (-1/2,1/16).
Область DV(i/4,i/2) имеет вершины (1/2,15/16), (3/4,9/16),
(3/4,7/16), (1/2,1/16), (-1/4,7/16), (—1/4,9/16).
$3. Дуальность L-разбиений и DV-разбиений
1°. Пусть дано нормальное разбиение Т = {Т1,Тг,Тз,...}
пространства Е2. Мы будем обозначать грани разбиения за-
главными буквами с верхними индексами 0, 1, 2 (размерности
граней). В дальнейшем неотрицательные целые числа гид,
возможно с индексами, будут удовлетворять следующему со-
отношению: т + q = 2.
Определение. Два нормальных разбиения Г и ЯЛ пло-
скости Е2 назывются комбинаторно-метрически дуальны-
ми, если существует взаимно однозначное соотвествие между
гранями разбиений Т и ЯЛ, при котором выполнены следую-
щие условия:
1) Граням размерности г >0 разбиения Т (ЯЛ) ставятся
в соотвтствие грани размерности q разбиения ЯЛ (Т).
2) При данном соответствии включение Р С Р (Mq С
М4'} влечет за собой включение М4' С Mq (Tr С Р).
3) Каждые две соответствующие друг другу грани разби-
ений Т и ЯЛ взаимно перпендикулярны.
(При выполнении только двух первых условий нормаль-
ные разбиения Т и ЯЛ назывются комбинаторно дуальны-
ми.)
29
2°. Теорема 2.10, п.2. Для любой < 1,1 >-системы
D С Е2 разбиения { DV}e и {L}e комбинаторно-метрически
дуальны.
о Для начала отметим, что каждая вершина разбиения
{Д}£, являясь точкой системы 27, есть центр некоторого мно-
гоугольника из разбиения Наоборот, центр каждого
многоугольника из разбиения {DV)e, являясь точкой систе-
мы 27, есть вершина разбиения {L}e- То есть, вершины раз-
биения {£}д и многоугольники разбиения {BVlr находятся
во взаимно однозначном соответствии.
Центры описанных вокруг многоугольников разбиения
{Т}£ кругов и только они обладают тем свойством, что мно-
жество удаленных от них на минимальное расстояние точек
системы 27 имеет ранг 2. Поэтому множество этих центров
совпадает с множеством вершин разбиения {ВП}£. То есть,
многоугольники разбиения {Т}^, и вершины разбиения
{DV}r находятся во взаимно однозначном соответствии.
Из построения полученного соответствия следует, что
оно удовлетворяет первым двум условиям дуальности. Тре-
тье условие здесь тривиально. Таким образом, существует
естественная дуальность разбиений {DV}e и {А}гв нулевой
и максимальной размерностях.
Рассмотрим произвольное ребро L1 С {Д}г, с вершина-
ми А и В. Оно является общим ребром двух многоугольников
разбиения {L}е> которые мы обозначим через Ly и Ь2. Обо-
значим через Oi и О2 центры кругов Lj и L2, описанных около
многоугольников L] и L2 (см §2 рис. 2.09). Согласно сказан-
ному выше, точки C>i и О2 суть 0-мерные грани (вершины)
каких-то многоугольников множества Покажем, что
среди них содержатся многоугольники DVa и DV&, а отре-
зок (ДО2 есть их общее ребро, т.е. 1-мерная грань разбиения
{ГЖ} Е- Напомним, что прямая О]О2 есть серединный пер-
пендикуляр к общей хорде АВ кругов L* и L*2, т.е., согласно
определению, многоугольник DVa лежит относительно пря-
30
мой О] О2 в полуплоскости, содержащей точку А. Также заме-
тим, что серединные перпендикуляры отрезков, соединяющих
точку А с вершинами многоугольников L\ и (исключая А
и В), пересекают прямую О1О2 в точках б)] и О2 соответст-
венно. А серединные перпендикуляры отрезков, соединяющих
точку А с другими точками X € 27, пересекают прямую O1O2
вне отрезка ОгОг (см. рис. 2.09). Следовательно, отрезок
является ребром многоугольника ВУд. Аналогично для
многоугольника ВУд.
Рис 2.09
Сопоставим каждому ребру L1 С {Д}д построенное реб-
ро 0^02 С {ВУ}д. Из построения такого соответствия вид-
но, что для каждого ребра L-разбиения найдется ребро DV-
разбиения и наоборот. Причем ребро L1 перпендикулярно
ребру ОХО2.
Докажем, что так построенное соответствие между реб-
рами (1-мерными гранями) L-разбиения и ребрами (1-мер-
ными гранями) ВУ-разбиения является взаимно однознач-
ным.
Предположим, что это Fie так. Пусть некоторому ребру
31
L-разбиения соответствует два разных ребра ДУ-разбиения.
Тогда эти два ребра должны иметь одинаковые концы. Пусть,
наоборот, некоторому ребру ДУ-разбиения соответствует два
ребра L-разбиения. Тогда эти два ребра должны лежать на
одной прямой и иметь общую середину.
Таким образом, построено соответствие между одномер-
ными гранями, удовлетворяющее условиям дуальности (1) и
(3). Условие (2) проверяется непосредственно. Итак, разбие-
ния {ДУ}г и {L}r комбинаторно-метрически дуальны.»
3°. Как следствие доказательства теоремы 2.10 получаем
важный факт:
Лемма 8. Существует взаимно-однозначное соответст-
вие между L-ребрами и парами смежных по соответствую-
щему ребру DV -многоугольников. Каждое L-ребро перпен-
дикулярно прямой, содержащей соответствующее DV-ребро,
и делится этой прямой пополам, о»
Это дает возможность ввести следующее:
Определение. Каждое ребро L-разбиения с вершиной в
точке А с приданным ему направлением от точки А называ-
ется вектором смежности области DVa-
Теорема 2.11, п.п. Пусть дана система Делоне Е, то-
гда: если разбиение Ly симплициально, то разбиение DVy
примитивно. Обратно: если разбиение DV% примитивно, то
разбиение Le симплициально. (См. рис. 2.10.)
о Утверждение прямо следует из дуальности разбиений.»
4°. См. пункт 5° §1.
Теорема 2.12, п.п. Для произвольной системы Дело-
не Е и любого числа t > 0 найдется такая е-близкая к ней
система Делоне Е', что разбиение DVyy примитивно.
Утверждение прямо следует из теоремы 2.4, а также ду-
альности разбиений.
Теорема 2.13, п.п. Для произвольной системы Делоне
Е, дающей примитивное разбиение DVr>, и любого ограни-
ченного множества F С Е2 найдется такое число t > 0, что
32
любая t-близкая к система Д система Делоне Д', отличаю-
щаяся от системы Д лишь на t-окрестности множества F,
обладает примитивным DV-разбиением. £>•
5°. Пример 1. Рассмотрим разбиение Тд, а также си-
стемы 27] и 27г (см. §2, пункт 4, рис. 2.06). Очевидно, что
£)Р-разбиением для системы 27г является разбиение 1д. Най-
дите L-разбиение для системы 27].
Пример 2, Рассмотрим систему Делоне 27, построен-
ную в пункте 3. §2 (рис. 2.07). Очевидно, что здесь есть DV-
области двух и только двух видов: с целыми и с дробными
центрами. Постройте эти области, пользуясь соответствием
между ребрами и вершинами DV- и L-разбиений.
33
Глава 3
Решетки
§1. Решетки, их основные реперы
1°. Рассмотрим в плоскости Е2 произвольный репер Е =
Е(О, е1,ег), т.е. два линейно независимых вектора ei,«2 с на-
чалом в одной и той же точке О G Е2, которую удобно считать
совпадающей с началом системы координат
Определение. Совокупность Ге всех точек плоскости
Е2, имеющих целочисленные координаты относительно репе-
ра Е, т.е. множество точек д = д^е} + <72^2, где <71,52 € Z,
называется 2-мерной точечной решеткой или просто ре-
шеткой (рис. 3.01). (Ниже, если нам будет не важно, относи-
тельно какого репера задается решетка Ге, будем обозначать
Другими словами, решетка Г есть аффинный образ це-
лочисленной решетки Z2 = {(£i,&) : Е\,Е2 С Z).
Всякий репер, задающий решетку Г, называется ее ос-
новным репером, а параллелограмм Л(Е), построенный на
34
любом основном репере £, - основным параллелограммом
решетки, будем обозначать его площадь через $(£).
Вектором решетки называется любой вектор, равный
вектору, имеющему начало и конец в точках решетки, т.е.
любой вектор с целочисленными координатами относительно
произвольного основного репера решетки.
Мы также будем рассматривать l-мерные решетки, т.е.
множества всех точек вида {ке : к € Z}, где е - произвольный
вектор с фиксированным началом. Мы будем иногда назы-
вать точку 0-м.ерной решеткой.
Любое подмножество Г\ решетки Г, само являющееся ре-
шеткой, называется подрешеткой решетки Г.
35
Теорема 3.1, n.n. Для любой решетки Гг справедливы
следующие три утверждения:
(1) Каждый репер 8' = (О', е^ег), гДе О' G Г, является
основным для решетки Г, (рис. 3.02).
(2) Решетка симметрична относительно каждой своей
точки.
(3) Решетка симметрична относительно середины каж-
дого отрезка, соединяющего две произвольные ее точки (рис.
Рис. 3.03
t> Докажем (3). Рассмотрим любые две точки Р и Q ре-
шетки Г с координатами (рьрг) и (91,9г) относительно ре-
пера 8. Тогда координаты середины R отрезка PQ равны
Возьмем теперь произвольную точку X G Г с
координатами (х1,хг), тогда, как легко видеть, симметрич-
ная ей точка относительно точки R будет иметь координаты
36
(Pi + 9i — a’l, P2 + 92 — -1'2), т.е. целочисленные координаты от-
носительно репера Е. Утверждение (3) доказано.
Отсюда, при Р = Q, получаем доказательство утвержде-
ния (2).
Утверждение (1) очевидно. •
Следствие утверждения (1). Каждая решетка является
трансляционно правильным множеством.
2°. Лемма 1, п.п. Целочисленная матрица L унимоду-
лярна тогда и только тогда, когда обратная ей матрица L~l
целочисленна. t>*
Множество всех целочисленных унимодулярных (2 х 2)-
матрип обычно обозначается через GL(2,Z).
Два репера Е = ЕЦР е-^&Ц и £' — (0,6]',62') называются
целочисленно унимодулярно эквивалентными, если ма-
трица перехода от одного из них к другому целочисленна и
унимодулярна.
Два репера Еу — 8(P,pi,P2) и £2 = £(<2,91,9г) будем назы-
вать эквивалентными, если один из них, например Е\, кон-
груэнтен такому реперу Е-А, который целочисленно унимоду-
лярно эквивалентен реперу Е2.
Теорема 3.2, п.п. Пусть решетка Г задана репером
Е = Е(О, 61,62). Репер £' = (О. е/, е2')> гдее.\, е.2 векторы
решетки Г, является основным репером решетки Г тогда и
только тогда, когда он целочисленно унимодулярно эквива-
лентен реперу Е,
t> Пусть репер £' является основным репером решетки Г.
Рассмотрим целочисленную матрицу L, строки которой суть
координаты векторов с/, е2 относительно репера Е. Строки
обратной матрицы L~x это координатные строки векторов
e.i,e-2 относительно основного репера Е'. То есть, матрица
L-1 также целочисленна. Но тогда из леммы 1 следует, что
Д SG'L(2,Z).
Если матрица перехода от репера 8 к реперу Е' целочис-
ленна и унимодулярна, то легко проверить, что любая точка
37
решетки Г имеет целочисленные координаты относительно
репера <£', т.е. репер £' основной.»
Таким образом мы установили взаимно однозначное со-
ответствие между классами целочисленной унимодулярной
эквивалентности реперов с началом в точке О и решетками с
тем же началом.
Пользуясь этим, мы очевидным образом устанавливаем
взаимно однозначное соответствие между классами эквива-
лентности реперов и классами попарной конгруэнтности ре-
шеток.
3°. Пусть векторы С] и ег произвольного репера £ =
£(0,61,02) относительно системы (£i,£2) имеют координаты
(£п,£21) и (£12,£22) соответственно. См. рис. 3.01. Тогда ре-
перу 8 ставятся в соответствие две. важные матрицы: Е -
координатная матрица и А - матрица Грама. Именно,
•= = ll£o II =
£11 £12
£21 £22
А = II «у II =
«11
«21
«12
«22
(ei,ei) (ei,e2)
(«1,6-2) («2, «2)
где через (•, •) обозначено скалярное произведение.
Как легко видеть, для этих матриц справедливо соотно-
шение А = EtE.
Заметим, что S£ = |detS| = V det А
Следствие 1, п.п. теоремы 3.2. Площади паралле-
лограммов, построенных на любых двух основных реперах
одной и той же решетки, равны между собой.
о В использованных обозначениях имеем:
S£. = \detЕ'| = |det(SL‘)| - \detS|\detL\ = \detS| = S£.»
4°. Пусть E — (61,62) - некоторый репер. Репером, вза-
имным реперу £, называется репер = (е/-1\ е-^-1)),
38
векторы которого удовлетворяют соотношениям (е,-,е/ ^) =
1, (е», е/-1)) = 0, где г / j.
Для репера Е, кроме, взаимного репера, рассматривается
также присоединенный репер Е*, составленный из векторов
е* = где А - матрица Грама репера Е.
Из равенств detA* = (detA)2det.A~x — (detА) следует, что

Отметим один из аспектов разницы между взаимным и
о о о о о о о
Рис. 3.04
присоединенным реперами.
1) Длины векторов взаимного репера f(~i) = е2(-1))
зависят от эталона длины, (п.п).
Суть этого проясняет такой пример. Пусть длина векто-
ра С] равна 2 см, а угол между векторами в] и е2^равен
39
тогда длина равна 1 см. Но если мы будем изначально
измерять длины векторов в миллиметрах, то длина вектора в]
не изменится, а длина будет равна Т мм, что, очевидно
не равно 1 см.
2) Длины векторов присоединенного репера Е* = (е/. е2*)
не зависят от эталона длины, (2.2). См. рис. 3.04.
Будем наливать решетки, заданные реперами £б-0 и £* у
соответственно взаимной и присоединенной к решетке Ге и
обозначать через и Г*.
Теорема 3.3, п.п. Решетка является взаимной к
заданной решетке Г тогда и только тогда, когда все скалярные
произведения (g,g') целочисленны, где g и д' векторы решеток
Г и соответственно.
Эта теорема дает арифметическую интерпретацию вза-
имной решетки. Поскольку она в дальнейшем нам не потре-
буется, то оставляем ее доказательство читателю.
§2. Реперы, решетки и положительно
определенные квадратичные формы (ПКФ)
1°. Здесь, как и всюду дальше, мы сохраняем все обозна-
чения пункта 3° §1.
Обозначим через .Гц-гг координаты любой точки X отно-
сительно репера Е. Тогда квадрат расстояния между точками
О и X равен
|ОХ|2 = (tjCj + х2е2, х-]в] -Ьх2ег) =
= + 2ai23-1X2 + «22^2 — fsfxiiPi) — fe-
Поскольку квадрат расстояния между несовпадающими точ-
ками положителен, квадратичная форма fa есть положитель-
но определенная квадратичная форма (ПКФ). Форма fe на-
зывается метрической формой репера Е. Подчеркнем, что
матрица формы Д- есть матрица Грама репера Е.
40
Таким образом, каждый репер плоскости задает (одну)
ПКФ от двух переменных. Очевидно следующее замечание
Замечание. Если два репера конгруэнтны, то они зада-
ют одну и ту же ПКФ.
Теорема 3.4, п.п. Каждая ПКФ от двух переменных
задает (с точностью до движения) репер плоскости Е2.
с> Рассмотрим ПКФ f = /(Ж1.Х2). Из линейной алгебры
известно, а при п = 2 тривиально доказывается, что такую
форму f можно разложить бесконечным числом способов в
сумму двух квадратов независимых линейных форм от пере-
менных ;Г1,;г2- Пусть мы имеем некоторое такое разложение:
/ = (Cll-i'l + C12^z)2 + (<21-^1 + ^22^г)2
Тогда форму f можно представить в следующем виде
7 — II Sll^I + 421^'1 + 422-^2 ||
£11^1 + €12^2
^21 -i-1 + 422^'2
— + ;Г2в2, +T2C2),
где ci и e2 линейно независимые векторы с координатами
(Cn,^2i) и (^12>ч2г)> т.е. после выбора точки О, задают репер
£’=£(О,е1,е2).
Метрика репера £ не зависит от выбора разложения фо-
рмы f в сумму квадратов и выбора точки С). Действитель-
но, длины векторов репера и скалярное их произведение за-
даются коэффициентами формы f однозначно. Совмести-
мость движением любых двух реперов с одинаковой метрикой
очевидна.»
Заметим, что теорема 3.4 проясняет геометрический
смысл различных разложений ПКФ в сумму квадратов.
Отметим также, что теорема 3.4 и предшествующее ей
замечание устанавливают взаимно однозначное соответствие
между ПКФ и классами конгруэнтности реперов.
41
Определение. ПКФ, соответствующая взаимному ре-
перу т.е. квадратичная форма, заданная обратной мат-
рицей для матрицы А формы f, соответствующей репе-
ру £, называется обратной по отношению к ПКФ fe и обо-
значается ПКФ /*, соответствующая реперу £* (присо-
единенному реперу к £), называется присоединенной формой
к форме Д.
2°. Пусть А и А' матрицы Грама произвольных основных
реперов £ и £' решетки Г. Пусть f(X) и f'(X'), где X =
X' = (х]',.Г2/У, метрические формы реперов £ и £’.
Пусть, наконец, как и в теореме 3.2, L - матрица перехода от
репера £ к £'. Тогда, очевидно, имеем X' = X = L*X
и
А' = LAL1. (3.1)
Рассмотрим ПКФ f и заданные матрицами А и А'.
Определение. ПКФ f и f (матрицы А и А') называются
эквивалентными (J ~ А ~ А'), если существует такая
матрица L G GL(2, Z), для которой выполнено 3.1.
Иногда форму f будем обозначать через Lf.
Собирая все сказанное в этом параграфе, мы можем ут-
верждать существование следующих важных взаимно одно-
значных соответствий:
1. Между классами целочисленной унимодулярной экви-
валентности реперов с началом в точке О и решетками с тем
же началом.
2. Между классами эквивалентности реперов и классами
конгруэнтности решеток.
3. Между отдельными ПКФ и классами конгруэнтности
реперов.
4. Между классами эквивалентности реперов и классами
эквивалентности ПКФ.
5. Между классами эквивалентности ПКФ и классами
конгруэнтности решеток.
42
Сразу же возникает задача о выборе в решетке одного
определенного ее основного репера. Эта задача решается в
так называемой теории приведения, которой посвящен следу-
ющий параграф.
§3. Теории приведения. Минимальный вектор.
Приведение по Лагранжу.
1°. Квадратичная форма / (репер Ef), выбираемая на ос-
нове специальных требований ("условий приведения") из клас-
са эквивалентности форм (реперов) (вообще говоря, не обя-
зательно положительных), называется приведенной формой
(репером), алгоритм такого выбора - алгоритмом приве-
дения. Так как класс эквивалентности {/} обычно задается
некоторым своим представителем - формой /0 (репером £/0),
то алгоритм приведения заключается в том, чтобы, исходя
из любой формы fo, отыскать приведенную форму f ~ /0. В
зависимости от тех или иных условий приведения известны
различные частные теории приведения.
Хотя требование единственности приведенной формы
(репера) для данного класса эквивалентности является жела-
тельным, в применяющихся на практике способах приведения
допускается для некоторых классов эквивалентности конечное
число приведенных форм (реперов). В таких случаях каждо-
му классу эквивалентности ставится в соответствие вся сово-
купность приведенных форм (реперов).
Первая теория приведения для ПКФ двух переменных бы-
ла построена только в 1768 г. Лагранжем, в 3° мы даем ее
геометрический вариант.
Вопросами приведения занимался также Гаусс, однако
задача приведения ПКФ трех переменных была решена толь-
ко Зеебером в 1831 г. Именно в рецензии на эту работу Зее-
бера Гаусс впервые ввел понятие решетки.
Исторически же первый разработанный алгоритм приве-
дения, пригодный для ПКФ любого числа п переменных, был
43
предложен А.Н. Коркиным и Е.И. Золотаревым.
Задача приведения является одной из первостепенных за-
дач в теории квадратичных форм, и к настоящему времени,
кроме способа Коркина - Золотарева, имеется ряд находя-
щихся в употреблении способов приведения (n-мерных, хотя в
деталях построенных только для нескольких первых значений
п): Эрмита - Минковского, Зеллинга - Шарва, Вороного. В
кристаллографии популярен метод приведения Делоне. Весь-
ма общий способ приведения, охватывающий в виде частных
случаев некоторые из названных выше способов, был предло-
жен Б.А.Венковым.
о - point of Г
» - point of Z2
Рис. 3 .05
2°. В дальнейшем, говоря о векторах решетки, будем счи-
тать, что их началом является точка О (начало решетки).
Лемма 2, п.п. В каждой решетке Г для любого R > 0
44
существует лишь конечное число векторов, по длине не пре-
восходящих R.
t> Возьмем круг I) радиуса R с центром в начале решетки
О и то аффинное преобразование, которое переводит решет-
ку Г в решетку Z2 (см. рис. 3.05). Образ круга D при этом
преобразовании есть ограниченное эллипсом множество, оче-
видно содержащее лишь конечное число точек.»
Определение. Минимальным вектором решетки на-
зывается каждый ее вектор, имеющий минимальную положи-
тельную длину.
Лемма 3, В каждой решетке Г € Е2 существуют мини-
мальные векторы (п.п), причем их число не больше 6. Такое
число минимальных векторов может быть только у решетки,
построенной на равностороннем треугольнике (2.2).
t> Существование минимальных векторов, очевидно, сле-
дует из леммы 2. Рассмотрим решетку Г 6 Е2 с началом в
точке О, а также окружность С с центром в точке О и радиу-
сом т, равным длине минимального вектора. Все векторы с
началом О и концами в точках пересечения С П Г минималь-
ны и их длина равна радиусу т. А значит, концы любых двух
таких векторов находятся на расстоянии не меньшем, чем т,
т.к. их разность есть вектор решетки. Или, что тоже самое,
число точек, попавших в пересечение С Г) Г, не может быть
больше 6.
Последнее утверждение леммы уже очевидно.»
3°. Определение. Основной репер £ = £(О, ei, ег) произ-
вольной решетки Г называется приведенным по Лагранжу,
если проекция каждого вектора на e.j, где i,j = 1,2; г j, не
превосходит и угол между векторами ei и ег не тупой.
Назовем fc-ым рядом решетки Г относительно репера £
совокупность — {ke-z + Zej}, где k G Z фиксированно, а I
пробегает все множество Z.
Алгоритм Лагранжа. Рассмотрим решетку Г (см.
рис. 3.06) с основным репером £ = £(О, с^ег). Пусть |ej| <
45
|еа| иначе изменим их нумерацию. Выберем в ряду Г* такой
вектор, проекция которого на вектор в] имеет длину не более
. Если эта проекция сонаправлена с вектором ег, то через
е2 обозначим выбранный вектор, а если не сонаправлена, то
противоположный выбранному.
Возможны два случая:
1) l«i| > |вг1 и 2) |в]| < |е'2|.
В случае 1) возвращаемся к началу алгоритма, взяв за
новый вектор ej вектор е2, а за новый вектор е.% - вектор е.\.
Лемма 4, 2.2. В случае 2) вектор в] есть минималь-
ный вектор решетки Г, а вектор е2 один из (не более, чем
4) кратчайших векторов, не коллинеарных вектору в]. Длина
проекции вектора в] на е2 не более, чем |е2|/2.
46
t> Обозначим через h расстояние между нулевым и пер-
вым рядами, т.е. между прямыми, несущими эти ряды Го’ и
Г/. Оценим величину 2 А. Имеем:
141’ — л2 < 2Л > V5I4I > KI.
Отсюда мы имеем, что в А-тых рядах, где |А| > 1 нет векторов
короче, чем е'2. А при |А-| = 1 в А-тых рядах, очевидно, не
может быть более. 4 векторов, имеющих длину [e^. Последнее
утверждение теоремы уже очевидно.*
Таким образом в случае 2) репер £(О, ci,e'2) приведен по
Лагранжу.
Теорема 3.5. Алгоритм Лагранжа конечен.
о На каждом следующем шаге алгоритма мы берем век-
тор e.j меньшим, чем брали на предыдущем шаге. Но век-
торов, имеющих длину меньшую, чем |е.]|, лишь конечное
число.*
Отметим, что в решетке может быть несколько приве-
денных по Лагранжу реперов с началом в точке О, но число
их конечно и все они попарно конгруентны. Доказательство
этого и разбор случаев предоставляем читателю.
Обратим внимание, что алгоритм Лагранжа является од-
ним из самых эффективных способов разыскания минималь-
ных векторов решетки, заданной произвольным основным ре-
пером.
В заключение, укажем условие на ПКФ, чтобы опреде-
ленный ей репер был приведен по Лагранжу.
Определение. ПКФ f = an^i + 2ai2Xi%2 + «22^2 называ-
ется приведенной по Лагранжу, если 2ai2 < an < «22, ai2 > 0.
§4. "Полуоткрытый" параллелограмм решетки.
Леммы Блихфельдта и Минковского
1°. Определение. Пусть задана решетка Г С Е2, точ-
ка А € Г и пара А = (aj, <22) линейно независимых векто-
ров этой решетки. Параллелограмм П(А,А), построенный
47
на этих векторах, называется параллелограммом решетки
Г.
Нам часто, в том числе и в этом параграфе, будет удобно
рассматривать параллелограмм П(Л,Д), как "полуоткры-
тый" параллелограмм, т.е. как множество всех точек вида
{ОА + aci + 0а2 | 0 < ci,/3 < 1}.
В частности, "полуоткрытый" основной параллелограмм
П(О,8) решетки Ге состоит из тех и только тех точек плоско-
сти Е2, которые имеют в репере 8 координаты (х],хг), удов-
летворяющие при i = 1,2 неравенствам 0 < х,- < 1.
В силу трансляционной правильности решетки всю пло-
скость можно (дизъюнктно) разбить на полуоткрытые парал-
лелограммы, т.е. имеет место теорема:
Теорема 3.6, п.п. Пусть дана решетка Г, заданная ос-
новным репером 8. Тогда всю плоскость можно представить
в виде:
E2=Jj(Af).
АчГ
Это разбиение плоскости на полуоткрытые параллелограммы
вида Л (А, 8) дизъюнктно (т.е. каждая точка плоскости при-
надлежит одному и только одному такому параллелограм-
му).
t> Пусть точка X € Е2 имеет относительно репера 8 коор-
динаты (хьхг), пусть также А = ([xj, [хг]), где через [] обо-
значен символ Антье. Тогда точка X, очевидно, принадлежит
паралл ело грамму /7(А,£) и не принадлежит никакому друго-
му параллелограмму вида П{В,8}, где В G Г \ {А}.*
Полученное в теореме 3.6 разбиение мы обозначим через
Заметим, что плоскость также может быть представлена
и в виде разбиения 1 на параллелограммы решетки Г, постро-
енные на произвольной паре (ai, аг) ее линейно независимых
векторов. Для доказательства достаточно взять решетку Гд
и разбиение Тд-
48
Лемма 5, n.n. Для того, чтобы какой-либо полуоткры-
тый параллелограмм П(О,А) решетки Г был основным, не-
обходимо и достаточно, чтобы, кроме точки О, он не содер-
жал никаких точек решетки.
С> Необходимость условия в силу теоремы 3.6 очевидна,
докажем его достаточность. Пусть дан полуоткрытый па-
раллелограмм П — П(О,А), где А = Л(а1,аг), в котором
нет точек решетки, кроме О. Тогда мы возьмем разбиение
Тд плоскости на параллелограммы, конгруентные паралле-
лограмму П. Поскольку в параллелограмме П нет никаких
точек решетки Г, кроме одной точки, то и ни в каком дру-
гом параллелограмме этого разбиения нет точек решетки Г,
кроме его начала (здесь мы воспользовались трансляционной
правильностью решеток Г и Гд). То есть, иными словами,
вся решетка Гд состоит только из точек решетки Г. Следо-
вательно, 11 есть основной параллелограмм решетки Г.»
Рис. 3.07
2°. Здесь мы для полноты изложения приводим знаме-
нитые леммы Блихфельдта и Минковского (см. рис. 3.07
и 3.08). Они приводятся без доказательств, которые можно
49
найти во многих источниках.
Далее мы будем считать, что на плоскости Е2 задана ре-
шетка Г2 с площадью основного параллелограмма S.
Теорема 3.7, п.п. (Лемма Блихфельдта). Пусть на
плоскости Е2 расположено множество М площади S(M) > S
(см. рис. 3.07). Тогда существует такой параллельный пере-
нос ty., <zro #(21(Л/)Г1Л2) > 2 (т.е. в множестве М найдется, по
крайней мере, одна пара точек, задающих ненулевой вектор
решетки Г2).
Блихфельдт больше всего известен, пожалуй, именно
этой чрезвычайно красивой леммой. Основные же его дости-
жения принадлежат теории упаковок. Здесь ему принадлежит
воистину великий результат: он нашел плотнейшие решетча-
тые упаковки равных шаров при п=6,7.Ь. Блихфельдт опуб-
ликовал теорему полностью еще в 1935 году, и до сих пор для
п > 8 никаких аналогов этой теоремы не известно.
Теорема 3.8, п.п. (Лемма Минковского о выпуклом
теле). Пусть М С Е2 - центрально симметричная выпуклая
фигура, с центром в одной из точек решетки Г2 {см. рис.
50
3.0&). Тогда, если S(M) > 4S, то фигура М содержит еще, по
крайней мере, одну точку решетки.
§5. Характеристические свойства решеток
1°. Из определения решетки непосредственно следует,
что решетка является <1,1 >-системой, а условие, при ко-
тором произвольная <1,1 >-система становится решеткой,
дает следующая теорема.
Теорема 3.9, и.п. Трансляционно правильная < 1,1 >-
система есть решетка.
t> Сначала докажем теорему в случае прямой Е1. По 72-
свойству на любом отрезке длины 272^ найдутся две точки
системы 27, у которых по r-свойству в окрестности радиуса
г к нет других точек системы.
Пусть между выбранными точками нет других точек си-
стемы. Тогда система есть решетка с базисным вектором,
идущим из первой точки во вторую.
Пусть
между выб-
ранными ' ’ д * ‘ ‘
точками есть • • /--—у
другие точки • • у • у
системы. То- • . у . у
гда по г-свой- . /.? /
ству их ко- ул ул*I
нечное число,
• • • а ।
а расстояние
между любы-
ми двумя из .....
них не превы- рис з 09
шает 2гд.
Возьмем две ближайшие точки и все сводится к предыдущему
случаю.
Рассмотрим теперь систему Делоне 27 на плоскости.
51
Возьмем любые две точки системы и проведем через них пря-
мую I (см. рис. 3.09). Пересечение системы 27 с прямой I есть
одномерная решетка. Выберем начало координат в одной из
точек этой решетки. По /^-свойству найдется точка А € S,
не лежащая на прямой I. Пусть параллелограмм, построен-
ный на векторе, проведенном к точке А из начала координат,
и базисном векторе одномерной решетки, не содержит дру-
гих точек системы. Тогда вся система 27, очевидно, является
решеткой. Пусть теперь в нашем параллелограме есть дру-
гие точки системы. По r-свойству их конечное число. То-
гда среди них выберем вместо точки А точку /?. ближайшую
к прямой, получаем новый параллелограмм. В силу тран-
сляционной правильности этот параллелограмм не содержит
точек системы, и мы приходим к первому случаю.*
Каждая из следующих двух теорем является непосредст-
венным следствием теоремы 3.9.
Теорема 3.10, п.п Каждая трансляционно правильная
< 1, 0 > -система 27 С Е2 является решеткой некоторого ранга
m < 2.
Теорема 3.11, п.п. Каждая трансляционно правильная
<1,1 > -система (т.е. каждая трансляционно правильная си-
стема Делоне) 27 С Е2 является решеткой ранга 2.
В заключение мы докажем теорему, как бы обратную тео-
ремам 3.11 и 3.12, которая окончательно устанавливает связь
между <1,1 >-системами и решетками.
Теорема 3.12, п.п. Каждая решетка Г ранга m < 2,
есть трансляционно правильная <1,0 >-система. Она явля-
ется системой Делоне тогда и только тогда, когда m = 2.
t> Следствие к теореме 3.1 фактический утверждает су-
ществование для решетки числа г из определения < 1,0 >-
системы. Трансляционная правильность решетки также ут-
верждается этим следствием. Тем самым, первая часть до-
казана.
Последнее утверждение очевидно.*
52
Глава 4
Параллелоэдры
§1. DV-разбиения и L-разбиения решеток
Лемма 1, 2.2. Никакой L-многоугольник решетки не
содержит тупых углов.
о Пусть М есть L-мно-
гоугольник данной решетки
Г и пусть он имеет тупой
угол между сторонами АВ
и ВС, см. рис. 4.01. Точка
D, симметричная точке В
относительно середины от-
резка АС, принадлежит ре-
шетке Г (теорема 3.1) и ле-
жит внутри L-круга, грани-
ца которого определена точ-
ками А, В к С. Таким образом, многоугольник М не явля-
ется L-многоугольником.*
Лемма 2. Никакой L-многоугольник решетки не имеет
более четырех вершин.
Рис. 4.02
t> Любой выпуклый многоугольник, имеющий более, чем
четыре вершины, имеет, по крайней мере, один тупой угол.*
53
Теорема 4.1, 2.2. Каждый L-многоугольник для дву-
мерной решетки есть либо остроугольный треугольник, либо
прямоугольник, о*
Теорема 4.2. Все L-разбиения двумерных решеток раз-
деляются на два типа аффинной эквивалентности:
ы.
Рис. 4.03
1) Общий (рис. 4.02). В этом типе звезда каждой верши-
ны L-разбиения состоит из 6 последовательно циклически при-
мыкающих друг к другу треугольников. Причем каждые два
смежных треугольника центрально симметричны друг другу
относительно середины их общего ребра.
2) Специальный (рис. 4.03). В этом типе звезда каж-
дой вершины L-разбиения состоит из 4 последовательно цик-
лически примыкающих друг к другу прямоугольников. При-
чем каждые, два смежных прямоугольника центрально симме-
тричны друг другу относительно середины их общего ребра.
t> Пусть в £-разбиении, отвечающем некоторой решетке
Г* 1 2, нашелся по крайней мере один треугольник. В силу тран-
сляционной правильности решетки и теоремы 3.1. мы можем
считать, что это треугольник О А В. рис. 4.04. По лемме
1 (и теореме 3.1) треугольники О АВ' и ОА'В симметрич-
ные треугольнику ОЛВ относительно середин сторон ОА и
54
ОВ, соответственно, суть L-треугольники. Подсчетом углов
убеждаемся, что точки О, А' и В' лежат на одной прямой. По-
этому треугольниками О В' В",О А" В",О А' А" симметричны-
ми относительно точки О треугольникам О А'В, О АВ, О АВ1,
соответственно, завершается построение L-звезды точки О.
В силу трансляционной правильности решетки и теоремы 3.1
построена и L-звезда каждой точки решетки Г. Эти звезды,
очевидно, удовлетворяют описанию общего типа данному в
Рис. 4.05
Рис. 4.04
Пусть в L-разбиении, отвечающем некоторой решетке Г2,
нет ни одного треугольника. Тогда все L-многоугольники в
этом разбиении суть прямоугольники. То, что это разбиение
удовлетворяет описанию специального типа, данному в тео-
реме, легко проверяется, см. рис. 4.05.»
Определение. Решетка назывется общей, если ее L-раз-
биение имеет общий тип, и специальной, если ее L-разбиение
имеет специальный тип.
Теорема 4.3, -2.2. Область Вороного-Дирихле двумер-
ной решетки есть либо прямоугольник (для специальной ре-
шетки), либо центрально симметричный вписанный шестиу-
гольник (для общей решетки).
Обратно. Для каждого прямоугольника (каждого цен-
55
трально симметричного вписанного шестиугольника) найдет-
ся решетка, для которой эта фигура есть DV-область.
о Используем дуальность DV- и L-разбиений. Напомним,
что все вершины DV-области точки О G Г2 суть все центры
кругов, описанных вокруг многоугольников L-звезды точки О.
В общем случае имеем шестиугольник. Он центрально
симметричен, так как центрально симметрична L-звезда. Он
вписанный, так как все треугольники L-звезды попарно равны.
Специальный случай совсем тривиален.
Обратно. Рассмотрим произвольный выпуклый центра-
льно симметричный вписанный шестиугольник М с верши-
нами U, V, W, X, У, Z и с центром О (рис. 4.06). Обозначим
через A,B,C,D,E,F точки, симметричные точке О относи-
Заметим,
см. рис. 4.06,
что, поскольку
шестиугольник
М вписанный,
имеем О А = OZ
+OU, OB = OU
+<9У, ОС = OV
+OW. и что, по-
скольку шестиу-
гольник М цен-
трально симме-
тричен, имеем
OZ + OW = 0. Следовательно, О В = О А + ОС. Отсюда,
опять-таки в силу центральной симметрии шестиугольника
М, вытекает, что у точек А, В, С, D, E,F в репере {ОА, ОС}
целые координаты, т.е. эти точки принадлежат решетке Г2,
натянутой на указанный репер.
Далее, параллельно перенеся треугольники АОВ, ВОС,
COD, DOE, EOF и FOA всеми векторами решетки Г2, мы,
56
очевидно, получим триангуляцию Т всей плоскости, совме-
стимую с решеткой Г2.
Теперь отметим, что у каждого выпуклого центрально
симметричного вписанного многоугольника, кроме прямоу-
гольника, все углы тупые. (Мы оставляем доказательство это-
го элементарного факта читателю.) Учитывая это замечание
имеем, что все углы треугольников АОВ, ВОС, COD, DOE,
EOF и FOA как дополнительные к углам шестиугольника М
острые. Из этого, в свою очередь, следует выполнение необхо-
димого и достаточного признака того чтобы триангуляция Т
была L-разбиением. Действительно, к каждой стороне остро-
угольного треугольника из триангуляции Т примыкает своей
стороной центрально ему симметричный треугольник триан-
гуляции Т. Очевидно, что в круг, описанный вокруг одного
из этих треугольников, не попадает третья вершина другого.
Таким образом, триангуляция Т есть L-разбиение, от-
вечающее решетке Г2. И, согласно определениям, шести-
угольник М есть DV-многоугольник решетки Г2 с центром в
точке О.
Случай специального типа тривиален.*
§2. Перечисление всех параллелоэдров на плоскости.
Определение. Выпуклый многоугольник Р называется
параллелоэдром тогда и только тогда, когда существует раз-
биение ф, каждый элемент которого параллельно конгруентен
многоугольнику Р.
Если разбиение ф нормально, то параллелоэдр Р назы-
вается нормальным, иначе ненормальным. Если разбиение
ф примитивно, то многоугольник Р называется примитив-
ным, иначе непримитивным.
Теорема 4.4, 2.2. Каждый параллелоэдр, который не
является нормальным, есть параллелограмм. Каждый па-
раллелограмм может выступать как в качестве нормального
57
параллелоэдра, так и в качестве ненормального параллелоэд-
рах>»
о Пусть разбиение ф на параллелоэдры, параллельно кон-
груентные параллелоэдру Р, не нормально, тогда найдется
сторона АВ параллелоэдра Ро € ф, содержащая точку С -
вершину некоторых параллелоэдров Pi и Р2, прилегающих
к стороне АВ по сторонам DC и СЕ соответственно (рис.
4.07.а).
Рис. 4.07
Для удобства будем считать, что отрезок АВ горизонта-
лен, Ро расположен сверху от АВ, а Р1 и Р2 снизу от АВ,
как показано на рис. 4.07.а). Поскольку к прямой АВ примы-
кают параллелоэдр Ро сверху, а Р] и Р2 снизу, то у каждого
параллелоэдра разбиения ф есть "верхнее" и "нижнее" гори-
58
зонтальные ребра (пока неизвестно, что они имеют одинако-
вую длину). Параллелоэдр Р2 может быть совмещен парал-
лельным переносом с параллелоэдром Р]. Поэтому (верхняя)
сторона СЕ параллелоэдра Р2 равна (верхней) стороне DC
параллелоэдра Pj. Таким образом, верхняя сторона любого
паралелоэдра из нашего разбиения равна DC = СЕ.
Сторона CF (рис. 4.07.а,Ь) параллелоэдра Р2, прилежа-
щая к вершине С и отличная от DC, совпадает со стороной
CF* параллелоэдра Pi, прилежащей к вершине С и отлич-
ной от СЕ. Во-первых они лежат на одной прямой, иначе мы
можем выбрать такую точку X, не принадлежащую паралле-
лоэдрам Pi и Р2, лежащую ниже АВ и при этом достаточно
близко к точке С, что любой параллелоэдр разбиения ф, по-
крывающий ее, будет иметь общие внутренние точки с мно-
гоугольниками Pj й (или) Р2, см. рис. 4.07.Б. Аналогично
получаем, что F = F*. Из этого следует, что стороны па-
раллелоэдров Р] и Р2, прилежащие к вершинам D, Си Е,
параллельны и равны друг другу.
Далее, очевидно, что нижние ребра параллелоэдров Р) и
Р2 лежат на одной и той же прямой. Отсюда и из рассужде-
ния, прежде использованного дважды (рис. 4.07.с), получаем,
что точка F должна лежать на упомянутой прямой.
Второе утверждение теоремы очевидно.*
Теорема 4.5, 2.2. Каждый нормальный параллелоэдр,
который не является параллелограммом, есть центрально
симметричный шестиугольник.
Каждый центрально симметричный шестиугольник есть
нормальный параллелоэдр.
t> Рассмотрим произвольный нормальный параллелоэдр
Ро и разбиение ф, на нем построенное.
Во-первых, заметим, что для каждого ребра нормально-
го параллелоэдра, очевидно, найдется ребро, равное ему и па-
раллельное. Пусть у параллелоэдра Ро это будут ребра АВ и
А'В', рис. 4.08. В силу выпуклости параллелоэдра, стороны
59
ВС и В' ГУ параллелоэдра Ро должны лежать вне параллело-
грамма АВ В' А'.
Пусть к ребру АВ параллелоэдра Р() прилежит паралле-
лоэдр Рр Он имеет в числе других ребро В Г), отвечающее
ребру В'D'. Ребру ВС отвечает ребро В'С. У параллелоэдра
Ро найдется пара ребер, соответственно равных и параллель-
ных ребрам ВС и В' ГУ. Эти ребра, в силу выпуклости много-
угольника Ро, не могут находиться в цепочке его ребер, соеди-
няющих точки D' и С и не содержащей ребро АВ. Покажем,
что они должны иметь общую вершину В" G Ро- Действи-
тельно, параллелоэдр Рз примыкающий к параллелоэдру Ро
по ребру ВС, должен иметь пару ребер, равных и параллель-
ных ребру BD. Эти два ребра должны располагаться внутри
замкнутого угла DBC, но не могут, в силу выпуклости
Рис. 4.08
многоугольника Р3, оба находиться строго внутри угла DBC.
Следовательно, одно из них должно совпасть с BD. Иными
словами, ребра ВС и В Г) (В'С' и В' ГУ) суть ребра одного
60
и того же параллелоэдра Р3 (Р4) смежные в точке Б (В'\
Существование нужной точки В" G Ро уже очевидно.
Рассмотрим такой параллельный перенос Л, что Л(Р1) =
Ро и Л(Р0) = Р2- Очевидно, что Д(Р3) — Р4- Таким образом,
параллелоэдры Р3 и Р4 имеют общее ребро А'" В'", равное и
параллельное ребру АВ.
Треугольник А"'[)'С находится строго в полосе между
прямыми АВ и А'В', поэтому в нем не может содержаться
цельного параллелоэдра из разбиеия ф. Следовательно, каж-
дая точка треугольника А'", D' и С принадлежит по крайней
мере одному из параллелоэдров Ро,Р3 и Р4. Последнее, ес-
ли все три точки не совпадают между собой, противоречит
выпуклости многоугольников Р0,Р3 и Р4.
Поскольку точки [)' и ( ' совпадают, совпадают и точки
А с I)", а также С" с А'. Итак параллелоэдр Ро есть шестиу-
гольник.
Второе утверждение теоремы очевидно.»
§3. Основные теоремы о параллелоэдрах
После завершенного сейчас вывода всех параллелоэдров
на плоскости, становятся очевидными или почти очевидными
в двумерном случае многие теоремы, которые справедливы
(но трудно или очень трудно докалываются) для параллелоэд-
ров любой размерности.
Теорема Минковского, п.2 Каждый параллелоэдр цен-
трально симметричен.
с> См. теоремы 4.4 и 4.5.»
Теорема Венкова, п.2. Каждый параллелоэдр, кото-
рый не является нормальным, может выступать и в качестве
нормального параллелоэдра.
с> См. теорему 4.4.»
Теорема Вороного, п.2. Каждый примитивный па-
раллелоэдр аффинно эквивалентен DV-области некоторой ре-
шетки.
61
о Согласно теоремам 4.4 и 4.5, каждый примитивный дву-
мерный параллелоэдр есть центрально симметричный (вы-
пуклый) шестиугольник. Нам осталось доказать, что каждый
такой шестиугольник аффинно эквивалентен вписанному.
Сперва мы докажем удобным нам методом хорошо из-
вестный факт, что вокруг каждого такого шестиугольника
можно описать эллипс. Возьмем четыре из шести вершин
нашего шестиугольника (рис. 4.09), образующие параллело-
грамм, и аффинно преобразуем этот параллелограмм в пря-
моугольник, стороны которого назовем "вертикальными" и
"горизонтальными". Наш прямоугольник определяет семей-
ство эллипсов, пре-
дельные фигуры ко-
торого суть горизон-
тальная и вертика-
льная полосы, опре-
деляемые сторона-
ми прямоугольника.
()бразы оставшихся
двух вершин шести-
угольника лежат, в
силу его выпуклос-
ти, в одной из этих
семейства один эллипс.
Рис. 4.09
полос и выделяют из построенного
Вспомогательное утверждение доказано.
Преобразовав этот эллине в круг, мы докажем теорему.»
Замечание. Аналогичная теорема доказана Житомир-
ским для большого класса непримитивных параллелоэдров.
И, хотя двумерные непримитивные нараллелоэдры к этому
классу не принадлежат, каждый из них, очевидно, аффинно
эквивалентен .DV-области некоторой решетки.
Следующая теорема является как бы теоремой единст-
венности к теореме Вороного, как теореме существования.
62
Теорема МРС (Мишель, Рышков, Сенешаль), п.2.
Пусть параллелоэдр аффинно эквивалентен DV -области I)
некоторой решетки. Тогда, если эта область Г) не является
прямым произведением двух (или нескольких) DV-областей
решеток меньшей размерности, то она, с точностью до пре-
образования подобия, единственна.
с> Сначала заметим, что прямоугольник есть прямое про-
изведение двух одномерных DИ-областей (отрезков) и поэто-
му для него теорема не (формулируется и не верна: суще-
ствует континуум гиперболических поворотов, переводящих
прямоугольник в прямоугольники с другими отношениями
сторон. Поэтому рассмотрению подлежит только случай ше-
стиугольных параллелоэдров.
Итак, пусть задан центрально симметричный (выпук-
лый) шестиугольник М, для которого существует два аф-
финных отображения Л и Б во вписанные шестиугольники.
Мы можем, произведя, если нужно, преобразование подобия,
считать, что эти шестиугольники вписаны в один и тот же
круг С. Произведем аффинное преобразование Л/З-1. При
этом один из вписанных шестиугольников перейдет в другой,
и, следовательно, круг, в который они вписаны, перейдет в се-
бя. Но единственный вид аффинного преобразования круга в
себя есть движение.*
§4. О результатах при п > 2
Теорема Фёдорова. При и = 3 каждый параллелоэдр
есть аффинный образ DV-области решетки. При п = 3 име-
ется лишь один тип (комбинаторный тип) примитивных па-
раллеоэдров и четыре типа непримитивных, см. рис. 4.10.
Теорема Делоне. При v = 4 каждый параллелоэдр есть
аффинный образ DV -области решетки. При п = 4 имеется
три типа (комбинаторных типа) примитивных параллелоэд-
ров и 49 типов непримитивных.
63
Теорема РБ (Рышкова-Барановского). При п = 5
имеется 221 тип примитивных параллелоэдров.
Теорема Делоне в своей части о примитивных паралле-
лоэдрах и теорема БР существенно опираются на теорему
Вороного из предыдущего параграфа. В теореме РБ исполь-
зованы не определенное здесь понятие типа параллелоэдра,
до сих пор не известно, совпадает ли оно при п > 4 с по-
нятием комбинаторного типа параллелоэдра. при п = 5 это
по-видимому так.
До сих пор не известно является ли при п > 4 каждый 71-
мерный (непримитивный) параллелоэдр аффинным образом
DV-области решетки.
64
Глава 5
Плотность
§1 Звездные множества. Измерительные фигуры
1°. Определение. Множество М С Е2 называется звез-
дным относительно точки О Е М {центра ), если для любой
точки А € М интервал О А принадлежит множеству М (рис.
5.01).
Множество М С Е2
мы будем называть
сильно з в ездным отно-
сительно точки О Е М,
если у точки О сущест-
вует такая окрестность
U {окрестность зве-
здности), что относи-
тельно любой точки
О' Е U множество М
Рис. 5.01
звездно.
Мы будем всюду
считать, что, как толь-
ко задано звездное множество, задан и его центр.
Мы в дальнейшем будем рассматривать звездные множе-
ства двух видов: ограниченные замкнутые многоугольники,
не .обязательно выпуклые, (с центрами, не-лежащими на их
границах-) и ограниченные замкнутые выпуклые фигуры (с
центрами, не лежащими на их границах). Никаких других
звездных множеств мы в этой статье не рассматриваем.
Очевидно, что все звездные множества, рассматриваемые
нами, сильно звездны.
Пусть М - звездное множество с центром в точке О. Бу-
дем обозначать через гМ множество, гомотетичное множе-
ству М с центром в точке О и коэффициентом г > 0. Через
65
fr(Z') будем обозначать границу множества Z С Е1 2.
Теорема 5.1. Пусть дано звездное множество М с цен-
тром О. Для любого числа t > 0 найдется такое kt > О,
что для всех к > kt величина inf р(Х, У]) не зависит от к, где
X € fr(kM) fr((k + t)M).
t> Сперва заметим, что величина infp(X, У;) есть ниж-
няя грань непрерывной функции на компактном множест-
ве. Пусть infp(X, Yi) достигается на точках А € fr(kM') и
В, 6 fr((k + t)M).
Доказательство теоремы проведем отдельно (1) для вы-
пуклых фигур и (2) для звездных многоугольников.
Рис. 5.02
(1) Пусть М - (ограниченная замкнутая) выпуклая фигу-
ра. Отметим, во-первых, что весь отрезок АВ] (кроме точки
А) лежит, очевидно, вне фигуры кМ. Во-вторых, в точке В]
опорная прямая I' к фигуре (к 4- t.)M единственна, и она пер-
пендикулярна к А В] - иначе, см. рис 5.02, подвинув точку В],
мы получили бы меньшее расстояние. Отметим в третьих,
что среди опорных прямых к фигуре кМ в точке А есть пря-
66
мая I, перпендикулярная к АВ^ - иначе, см. рис. 5.03, фигура
кМ пересеклась бы с прямой I, и мы могли бы найти в фигуре
кМ точку, более близкую к точке Ву, чем А.
Рассмотрим теперь точку Л] 6 (k + t)M, отвечающую по
нашей гомотетии точке А. Через нее проходит опорная к фи-
гуре (к + t)M прямая /] параллельная прямой I и тем самым
прямой Таким образом, прямые Z] и как параллельные
между собой опорные прямые к фигуре (k+t)M, должны либо
совпадать, либо образовывать полосу заключающую эту фи-
Рис. 5.03
гуру. Поскольку отрезок ААг, также как и отрезок ABj, ле-
жит вне фигуры kM, фигуры kM и (k + t)M не могут лежать
внутри полосы между прямой /] и прямой Поэтому пря-
мые /] и I' совпадают. Таким образом, р(А,Аг) = а
это расстояние, очевидно, при изменении к не меняется, и
линейно по t.
(2) Здесь мы будем различать "выпуклые" и "вогнутые"
углы многоугольника М. Пусть EF и Е\Е, а также FG и
FiG’i, пары отвечающих друг другу по гомотетии ребер мно-
67
гоугольников кМ и (k + t)M. Несущие прямые этих ребер
обозначим через I, 1у, т и ту соответственно. При увели-
чении числа к длины указанных четырех ребер возрастают
(точки Е и G, а также Еу и G’], удаляются, соответственно,
от точек F и Fy). В то же время расстояния между прямыми
I и 1у (т и ту) не изменяются. Из сказанного ясно, что
для каждого t > 0 найдется такое kt > 0, что при всех к > kt
перпендикуляры, опущенные из точки F на прямые 1у и ту,
пересекут отрезки EyFy и FyGy, если угол EFG выпуклый (см.
рис 5.04), или перпендикуляры, опушенные из точки F] на
прямые I и т, пересекут отрезки EF и FG, если угол EFG
вогнутый (см. рис 5.05). За счет увеличения числа kt. в си-
лу конечности числа вершин многоугольника А/. можно до-
биться, чтобы описанная ситуация наблюдалась во всех углах
68
многоугольника kM. Далее мы полагаем, что число kt уже
выбрано таким большим.
Теперь уже ясно, что infp(>l, £?i) = р(/', Z"), где V и I" -
прямые, несущие некоторую пару отвечающих друг другу по
гомотетии ребер многоугольников кМ и (к + t.)M, а это рас-
стояние, очевидно, при изменении к не меняется и линейно
по £.•
(k+t)M
Рис. 5.05
Далее, стационарное по к значение величины В])
при заданном t мы будем обозначать через d(t).
Теорема 5.2. Величина d(t) есть линейная однородная
функция от t. То есть d(t) = Xt., где Л > 0 некоторая констан-
та, зависящая от звездного множества М и его центра.
t> См. доказательство теоремы 5.1.«
Пусть М есть звездное множество с центром О, и М' -
параллельно конгруэнтное (параллельное) ему с центром О',
69
соответствующим по конгруенции точке О. Будем обозначать
множество, гомотетичное множеству М' относительно точки
О', через гМ', где г > 0 - коэффициент гомотетии. Отметим,
что множества гМ и гМ' параллельно конгруентны друг дру-
гу с тем же переносом, что М и М'.
Теорема 5.3. Пусть р > О расстояние от О до О'. Тогда
при достаточно большом к > О для каждого р > 0 найдется
такое число t > 0, не зависящее от к, что
{к - t)M С кМ' С (к + t.)M.
d> Возьмем достаточно большое к > 0 и число Л из тео-
ремы 5.2 и положим t — 2р/Х. Тогда по теоремам 5.1 и 5.2
каждая точка множества кМ удалена от каждой точки мно-
жества E2\(k+t)M не менее, чем на 2р. В то же время каждая
точка множества кМ' отстоит от соответствующей ей точки
множества кМ на расстояние р. Отсюда сразу следует, что
кМ' С (к + t)M.
Включение (к — £)7W С кМ' мы можем получить либо
аналогичными рассуждениями, либо заменив в предыдущем
включении М на М', М' на М и к на к — £.•
§2. Плотность. Независимость плотности
от начала отсчета и граничных эффектов
1°. Под словом "функционал" мы здесь понимаем чи-
словую функцию от множеств Т С Е". Примерами могут
служить такие функционалы:
5i(T), тождественно равный 1 на всех Т С Е\
5</ — d(T), равный диаметру множества Т С Ег‘;
5s = равный площади множества Т С Е”.
Некоторые функционалы заданы не на всех множествах
Т С Е’1, например, на неизмеримых множествах функционал
5s не задан. Однако, в тех местах, где мы не конкретизируем
функционал, мы считаем, что на рассматриваемых множе-
ствах он задан.
70
Все рассматриваемые здесь функционалы мы будем счи-
тать принимающими на ограниченных множествах конечные
значения.
Обратим внимание, что во всех трех примерах функ-
ционал 5 обладает следующим свойством 5(Т) < '3(Т'), как
только Т С Т'. Это свойство мы будем называть монотон-
ностью функционала
Определение. Пусть задано некоторое локально конеч-
ное расположение Т ограниченных по совокупности множеств
{7}} (т.е. существует такое число С, что для любого 7} выпол-
няется неравенство fa < С), на которых задан функционал
fa Пусть также задано звездное множество М € Е2 (изме-
рительное тело) с центром в некоторой точке О. Нижней
плотностью функционала 3 относительно множества М на
расположении Т называется нижний предел
4 = АиСО = АиСГ.5) = limmf
где суммирование распространено на все множества 7} С гМ.
Определение. Пусть задано некоторое локально конеч-
ное расположение Т ограниченных по совокупности множеств
{Ti}, на которых задан функционал Пусть также задано
звездное множество М € Еи с центром О. Верхней плот-
ностью функционала § относительно множества М на рас-
положении Т называется верхний предел
Л = Дад(Т) = 4M(T,5) = Нт sup
г—»оо )
где суммирование распространено на все такие множества 7},
что Ti П 7-М / 0.
Определение. Плотностью функционала S относи-
тельно заданного измерительного тела М на расположении
5 называется число
дм(т,5) = ДМ(Т,5),
71
если 4w(S,5)=4m(^5)-
Примеры. Для функционала 51(7) (верхняя, нижняя)
плотность есть (верхнее, нижнее) среднее относительно мно-
жества М число элементов расположения Т. Для функциона-
лов d(T) и 5(7) плотность - это средний (относительно мно-
жества М) диаметр или площадь элементов расположения.
2°. Независимость плотности от начала отсчета.
Теорема 5.4, п.п. Пусть М есть сильно звездное множе-
ство с центром в точке О и М' параллельное ему множество с
центром в точке О'. Пусть Т - произвольное локально конеч-
ное расположение ограниченных по совокупности множеств,
на которых задан функционал 5(7). Тогда плотности Л, Л (и
Л, если Л = Л) фунционала 5(7) вычисленные относительно
множеств М и М', соответственно, совпадают.
t> Пусть Uо есть окрестность звездности множества Л/.
Заменив, если нужно, множества М и М' на гомотетичные им
с центрами подобия, соответственно, в точках О и О', предпо-
ложим, что О’ G Uo. Обозначим теперь через р > 0 расстоя-
ние от О до О'. Мы положим, что соотношения из теоремы
5.2 выполнены для некоторого t > 0, начиная с ko > 0, т.е.
для любого k > ko мы имеем:
(k - t)M С kM' С (к -I- t)M
Рассмотрим суммы Ег^(7Д и Ег$С^»)- Далее, в доказатель-
стве теоремы для Л (Л) суммирование распространяется на
все те множества 7}, что и при определении -Л (Л). Первую
из этих сумм берем при вычислениях связаных с множеством
М, вторую - с множеством М'.
В силу приведенных выше вложений имеем:
Еы №',) < П г(И) < Sffi)
Далее имеем:
s((k-t)M) £fc_t5№) E;g(7.)
S(kM) S((k - t)M) - S(kM) -
72
< s’(U + qm) Е^Ж)
- S(kM) S((k+t)M)'
Отсюда получаем:
(fc-02 Е^Ж) < Е^Ж) < (k + t)2
к2 S((k-t)M)~ S(kM') - № S((k + t)M)'
Переходя в случае Л к верхнему пределу при к —> оо и в случае
А - к нижнему, мы заканчиваем доказательство.*
3°. Независимость плотности от граничных эффектов.
Теорема 5.5, п.п. Пусть М - сильно звездное множе-
ство с центром в точке О. Пусть, также, Т - произвольное
локально-конечное расположение ограниченных по совокупно-
сти множеств, на которых задан монотонный функционал 5
и к > 0. Тогда значения пределов
.. - ГЕЖ) ЕЖ)
lim inf-^ / и hmsup^-E/
«> 6(rM) ,._«> S(rM)
не зависят от того, какие из множеств вида Т± пересекающихся
с множеством clos[(r 4- к)М \ (j— к)М] или какие подмноже-
ства этих множеств (помимо всех множеств вида Т, целиком,
лежащих в (т — к)М) учитываются в суммах. Эти пределы
равны, соответственно,
,• • .ЕЖ) г ЕЖ)
hminf~f и hmsup~. 4 /,
г-сс> S(rM) S(rM)
где суммирование может быть распространено как на все
множества Т, С (г — к)М, так и на все такие множества Т,,
что Т{ Г) (г 4- к)М 0.
о Обозначим через Е $(?}) СУММУ> в которой суммирова-
ние распространено на все Тг С (1—к)М, а также на некоторый
произвольный набор таких множеств Т, что 7i-O(r4- к)М 0
и подмножеств последних множеств.
73
Пусть диаметр каждого 7} G I не превосходит числа d.
Рассмотрим такое число t, что (см. теорему 5.2) d(t) > d.
Обозначим через 525(7^) сумму, в которой суммирова-
ние распространено на все Т; С (г — к — t)M, а через <?(7})
сумму, в которой суммирование распространено на все Ti С
(г + к + t)M. Учитывая монотонность функционала оче-
видно, имеем У)$(7}) < У'ЗСД) < 52Z/S(7i) или
S’((r-I--QM)£g(7;) < ГУ№) <
6'((r — к — ~ 6’(гЛ7) —
- S((r + k + t)M)S(rM)
Заметив, что, как и в теореме 5.4, верхний (нижний) предел
правой части равен верхнему (нижнему) пределу левой части,
мы заканчиваем доказательство.*
Имея в виду теоремы 5.4 и 5.5, в дальнейшем мы при
вычислении плотности функционала на расположении будем
пользоваться только сильно звездными измерительными те-
лами.
4°. Приведем один пример достаточно общего характе-
ра. Обратим сперва внимание, что доказанные теоремы о
независимости позволяют в этом примере не заботиться о
телах расположения ‘X, находящихся вблизи границы множе-
ства кМ и о положении измерительного тела М с точностью
до параллельного переноса. (Что же касается формы множе-
ства Л/, то дело, как мы увидим, обстоит совсем иначе.)
Рассмотрим плоскость Е2, заданную прямоугольной си-
стемой координат, и нижеследующее расположение X единич-
ных квадратов (см. рис. 5.06). Правая полуплоскость (х > 0)
разбита на такие квадраты с целыми вершинами, а левая по-
луплоскость не содержит внутренних точек ни одного из квад-
ратов расположения Т. Пусть функционал J имеет одно и
то же значение с на каждом квадрате расположения X Рас-
смотрим два сильно звездных множества Л/ и ЛГ с общим
74
центром - началом координат. Множество М определим как
прямоугольник с вершинами (—1,1), (2,1), (2, —1) и (-1,-1).
Множество М' определим как прямоугольник с вершинами
(—2,1), (1.1), (1, —1) и (—2, —1). Очевидно, что относительно
первого множества Л(Т, 5) = 2с/3, а относительно второго
Итак, мы видим, что плотность одного и того же функ-
ционала на одном и том же расположении, но относительно
различных измерительных тел, может оказаться различной.
Задача
Построить пример расположения, у которого плотность
относительно квадрата отличается от плотности относитель-
но круга (центры звездности обеих фигур взять в их центрах
симметрии).
}{3. Периодические расположения.
1°. Здесь и в Jj4 мы докажем ряд теорем, позволяющих, в
частности, относиться к понятию плотности не так пессими-
стично, как это возможно после примера из §2.
75
В дальнейшем, Т - это какое-либо локально конечное рас-
положение, на каждом элементе которого задан монотонный
функционал и М - заданная измерительная фигура. Как
и в §2, через 2^(5.%) (ЛдДТ, 3)) будем обозначать нижнюю
(верхнюю) плотность функционала 3 на расположении I, из-
меренную фигурой М. Если функционал 3 имеет на распо-
ложении Т плотность относительно измерительной фигуры
М, то мы обозначаем эту плотность через Ди(Т, 3)- Если
указанные плотности не зависят от фигуры М, то индекс М
мы опускаем.
Ниже нам несколько раз потребуется следующая констру-
кция. Возьмем на плоскости квадрат с центром в точке О
и с ребрами длины 1 параллельными осям координат. Да-
лее строим разбиение (квадрильяж) Q = qo ф Z2 плоскости
Е2. (Черед X ф Y здесь обозначена векторная сумма или
сумма Минковского, т.е. множество точек, заданное, всеми
векторами вида Ох + Оу, где х £ X, у £ У, а О - произвольно
выбираемая точка, в данном случае - начало координат.)
Через AQ, где Л > 0, мы будем обозначать квадрильяж.
гомотетичный квадрильяжу Q с коэффициентом ,\ и центром
О.
2°. Расположение Т называется периодическим, если оно
представимо в виде Т* © Г2, где Т* - некоторое конечное рас-
положение, а Г2 - решетка. См. рис 5.07.
Теорема 5.6, п.п. Для каждого периодического распо-
ложения Т — Т* © Г2 и каждого монотонного функционала
3 определена не зависящая от измерительной фигуры плот-
ность Л(Т, §).
о Произведя, если нужно, параллельные переносы, мы
можем считать, что начало решетки Г2 и одна из точек како-
го-то множества из расположения Т* находятся в точке О.
Возьмем произвольный основной параллелограмм По решет-
ки Г2 с вершиной в точке О и обозначим его диаметр через
d, а площадь - через S. Построим (аффинно эквивалент-
76
ное построенному выше разбиению Q) нормальное разбие-
ние Q' = По @ Г2 плоскости Е2 на параллелограммы вида
ПА — 21од(Ло), где А £ Г2. Параллелограмму ПА отнесем
конечное расположение 21<-м(Т*).
Пусть X* = {Т[,Т2, ,Tk}- Обозначим через d* диаметр
множества 7} U 7г О ... U 7*. Зафиксируем измерительную
фигуру М с началом в точке О.
Покажем, что Дц(Х, 5) = (Е* 5(7}))/5, гДе сумма
52* 5(7,) взята по всем Тг G X*.
Действительно, выберем число р > d + 2d*. Тогда, соглас-
но теореме 5.5, в выражениях
lim inf
ЕЖ)
5(rM)
и lim sup
7—>OG
ЕЖ)
S’(rM)
сумму J2 5(7}) можно считать взятой по всем элементам рас-
положения X, отнесенным тем параллелограммам разбиения
77
Q', которые лежат в множестве гМ. Эта сумма равна
ЛЕ*5(7]), где к число таких параллелограммов. Имеем
• ГЕЖ) .. • ЛЕ’Ж) ks
Inn 1111 — -- - = Lun пн-—-./ ;• =
»•—no ,S(r7Vf) r-.no kS S(rM)
= E’ Ж)
s
г г
liininf .
r-.no S(tM)
Согласно той же теореме 5.5, имеем lim infr—<х. s(rMj = 1, и.
УЛС6)
вычисляя точно так же lnnsup,—.^, , получаем
fЕЖ) ЕЖ) . ЛТЧ Е’Ж)
liininf - '' = lnnsup = АМ(Т) =-----------------
r-.no S(rM) г-оо S(rM) S
Но эта величина от М не зависит.*
В виде отдельного замечания еще раз отметим важный
факт, полученный в доказательстве теоремы 5.6.
Замечание, п.п. Для каждого периодического располо-
жения
Ъ={ТъТ2,...,Тк}®Г2
плотность равна (52Гм 5(7]))/Я(ПО) вне .зависимости от из-
мерительной фигуры.
§4 Независимость от измерительной фигуры плотностей
плотнейшей упаковки и редчайшего покрытия
1°. Упаковки. Пусть (Г} - некоторый набор множеств, по
диаметру не превосходящих числа d/2. В этом пункте через
‘I (быть может с различными индексами) будут обо начаться
упаковки в Е2 таких множеств 7], каждое из которых конгру-
ентно (быть может, заданным набором способов) одному из
множеств Т Е {71}.
78
Теорема 5.7. Для любой измерительной фигуры М,
любого t > 0 и любой упаковки То найдется такая перио-
дическая упаковка ‘Хом, для которой выполнено неравенство
Av (То) ~ Aw (Том) < е.
t> (’читаем фигуру М, число 1 > е > 0 и упаковку То,
заданными. Выберем такое a > 0, чтобы выполнялось нера-
венство
(а + с/)2 — а2 < ^еа2. (5-1)
Рассмотрим квадрильяж aQ и выберем (см. теорему 5.5)
к = а\[2 + d/2 и такое г0, чтобы, во-первых, при всех г > го
выполнялось неравенство
6TU2
5'(гЛ7)
где через о обозначено число квадратов квадрильяжа Q, ле-
жащих в множестве гМ. Во-вторых, выберем такое Ti > Го,
для которого выполнено также и условие
Aw (То)
ЕЭД) 1
5’(п/И) 3
где сумма взята по всем элементам упаковки То, пересекаю-
щимся с упомянутыми квадратами (теорема 5.5, к — а\/2 +
d/2). Отсюда имеем
Aw (То) —
ЕОД)
ста2 S(ryM)
1
—е.
3
Далее, поскольку ста2 < S(r}M), мы получаем
Аи(То)
ЕЗД) г 1,
ста2 3
79
Следовательно, среди наших а квадратов, в силу принципа
Дирихле, мы можем найти, по крайней мере, один квадрат
(обозначим его через Q), для которого
Дм(То) - < |е, (5-2)
где сумма взята по всем элементам упаковки То, лежа-
щим в квадрате Q' концентричном квадрату Q и гомотетич-
ном ему с коэффициентом (1 + ^) (в том числе по всем эле-
ментам упаковки То, пересекающимся с квадратом Q).
Кроме того, очевидно неравенство:
£Ж) (a + d)2 1
а2 аг 3 '
Произведем необходимые оценки, используя это неравенство,
а также неравенства (5.1) и (5.2):
1 1 , 1 X 1 2
<Г + з€(1 + зс)< 3c + 3e-t-
Построим упаковку Том- (Заметим, что при этом набор {Т}
может сократиться.) Для этого возьмем квадрильяж Q —
(a-l-cQQ и заменим в нем каждый из квадратов квадратом О'
вместе с той частью упаковки То, которая содержится в квад-
рате Q'. Согласно теореме 5.1 упаковка Том имеет плотность
Aw (Том), и эта плотность удовлетворяет, в силу неравенства
(5.3), требуемому неравенству.*
Отметим, что упаковка Том может иметь плотность
большую, чем исходная упаковка Т, подчеркнем, что это не
противоречит теореме 5.7.
80
Теорема 5.8. Каковы бы ни были измерительные фигу-
ры М и М', для упаковок вида % имеют место равенства
sup АМ(Т) = sup Аи(Т) = sup Аи-(Т) = sup ДМ,(Т).
(Наибольшая возможная плотность для упаковки вида ‘I не
зависит от измерительной фигуры.)
о Пусть для данной измерительной фигуры sup Ам(Т) не
достигается. Выберем е > 0 и такую последовательность упа-
ковок {Ту} (j = 1,2,...), что supAw(T) — Аи(Ту) < 2-?-1е.
Заменяя в теореме 5.6 число е на 2~3~1е (j — 1,2,...), мы по-
строим последовательность периодических упаковок {Тум},
для которых плотность (и тем самым нижняя плотность)
удовлетворяет неравенствам Аи(Ту) — Лм&зм} < 2“’"1е и,
следовательно, неравенствам
sup Aw(T) - Аи(Тум) = sup Аи(Т) - АМ(%Л1) < 2-Je. (5.4)
Тем самым, при любом j справедливо и неравенство
sup Аи(Т) -supAmC^m) < 2“’е,
а значит и неравенство
sup Aw (Т) < sup (Тум)-
С другой стороны, очевидно, что supAw(T) < sup Лм(Т), по-
этому первое и третье равенства из утверждаемой цепочки
равенств доказаны.
Далее. Так как все упаковки Тум периодические, то их
плотность не зависит от измерительной фигуры, т.е. для
любой другой измерительной фигуры М' выполнено равен-
ство Аи'(^ум) — Аи(Тум)- Такие же построения, как и для
sup AwT, можно провести для sup Aw<(T) и построить соот-
ветствующую последовательность Тум'- Для этой последова-
тельности так же, как и для последовательности Тум, имеем
81
Ли^М'} = Отсюда сразу следует справедливость
второго неравенства из утверждаемой цепочки.
Пусть для данной измерительной фигуры sup Дм (Т) до-
стигается на некоторой упаковке То- Последовательность
Т7д/, которая удовлетворяет неравенствам (5.4), строится в
этом случае непосредственно по упаковке То, и все дальней-
шие рассуждения сохраняются.*
2°. Покрытия. Пусть {TJ - некоторый набор множеств,
по диаметру не превосходящих числа d. В этом пункте через
Т (быть может, с различными индексами) будет обозначаться
произвольное (напомним, локально конечное) покрытие пло-
скости Е2 множествами 7), каждое из которых конгруентно
(быть может, заданным набором способов) одному из мно-
жеств Т G {7’}.
Лемма. 1 Для любой измерительной фигуры М вели-
чина inf zAjw(T) конечна.
о Обратим внимание на то, что все множества любого
локально-конечного покрытия и, тем самым, все множества
Т G {Т} не могут иметь нулевую площадь. Рассмотрим та-
кое множества 7' € {71}, что 5’(7’) > 0. Поскольку множе-
ство Т имеет положительную внутреннюю меру, в нем най-
дется квадрат q с ребрами, параллельными осям координат.
Обозначим длину ребра этого квадрата через е и рассмотрим
квадрильяж eQ. Разместим множество Т таким способом,
чтобы квадрат q совпал с квадратом квадрильяжа cQ. Пе-
риодическое покрытие Т ф eZ2 имеет плотность, не превосхо-
дящую
S(T)/t2 > inf Ди(Т)--
Теорема 5.9. Для любой измерительной фигуры М.
любого е > 0 и любого покрытия То найдется такое перио-
дическое покрытие е£цм, Для которого выполнено неравенство
Дм (Том) — Ам (Т) < t
с> ( ’читаем фигуру А7, число 1 > е > 0 и покрытие I.-.
заданными. Выберем такое a > 0, чтобы выполнялось нера-
82
венство
а2 - (а - cZ)2 < ; - cZ)2 = а(а - cZ)2.
•’ ±Дл/(£о)
(5.5)
Рассмотрим квадрильяж aQ и выберем (см. теорему 5.5)
k = а\/2 и такое г0, чтобы при всех т > ги выполнялось нера-
венство
ста2
° < 5(гМ)
(5.6)
где через ст обозначено число квадратов квадрильяжа aQ пере-
секающих множество 7*Л/. Будем считать, что для некоторого
числа и > т*о выполнено также и условие
ЕЗД)
5(7*1 Л1)
где сумма взята по всем элементам покрытия “Хо, пересека-
ющимся с упомянутыми квадратами (см. теорему 5.5). От-
сюда имеем
ЕЭД)
ста2 5(т*1 Л/)
4лт(^о) < «•
- ZW^o) <
Далее, поскольку ста2 > 5(7*1Л1), см. (5.6), мы получаем
ЕЭД) А
--—Т-----УлЯ-иД < л-
craz
Следовательно, среди наших ст квадратов, в силу принципа Ди-
рихле, мы можем найти по крайней мере один квадрат (обо-
значим его через Q), для которого
Е'ЭД)
- АиС^о) < rv,
(5-7)
83
где сумма взята по всем элементам покрытия То, лежа-
щим в квадрате Q. Эти элементы покрывают квадрат Q' кон-
центричный квадрату Q и гомотетичный ему с коэффициен-
том (1 — ^). Учитывая (5.5) и дважды (5.7), а также то, что
^м(^о) — произведем необходимые оценки:
Г Ж) < Е'ЭД) Л гт 1 <
(a-f/)2 С2 (a_J)2
<E^)(I+a)_A1(Io)<n+nS^< (5.8)
< cv + о(ДЛ/(Т0) + о) < |е(2 + |с) < с.
Построим периодическое покрытие Том- (Заметим, что при
этом набор {71} может сократиться.) Для этого возьмем квад-
рильяж Q' = (а — c/)Q и заменим в нем каждый из квадра-
тов квадратом Q' вместе с той частью покрытия То. кото-
рая содержится в квадрате Q'. Согласно теореме 5.6 покры-
тие Том имеет некоторую плотность Ди (Том) и эта плот-
ность удовлетворяет, в силу неравенства (5.8), требуемому
неравенству.»
Теорема 5.10. Каковы бы ни были измерительные фи-
гуры М и М1, для покрытий вида Т имеют место равенства
inf Ди(Т) = inf ДМ(Т) = inf ДМ,(Т) - inf Дщ(Т).
(Наименьшая возможная плотность для покрытия вида Т не
зависит от измерительной фигуры.)
о Пусть для данной измерительной фигуры inf Ду (Т) не
достигается. Выберем t > 0 и такую последовательность по-
крытий {Т7} (у = 1,2,...), что Дм(‘Д) — inf_lw(T) < 2 ч.
Заменяя в теореме 5.4 число е на 2~J-1t (j = 1.2. .). мы по-
строим последовательность периодических покрытий {Т-
84
для которых плотность (и тем самым верхняя плотность)
удовлетворяет неравенствам
Ди(Т3м) - inf (Т) < 2-’е
(5.9)
Поэтому так же, как и в теореме 5.8, первое и третье ра-
венства из утверждаемой цепочки равенств доказаны. Да-
лее. Так как все покрытия “Х7м периодические, то их плот-
ности не зависит от измерительной фигуры, т.е. для лю-
бой другой измерительной фигуры М' выполнено равенство
Ди'(Тум) = Те же построения можно провести
для inf Av/'(T) и построить соответствующую последователь-
ность T7,v', для которой «1v(T7m') = Дм'(^м')- Отсюда сразу
следует справедливость второго неравенства из утверждаемой
цепочки.
Пусть для данной измерительной фигуры inf ДМ,(Т) до-
стигается на некотором покрытии То- Последовательност!,
которая удовлетворяет неравенствам (5.9) строится в
этом случае непосредственно по покрытию “То, и все дальней-
шие рассуждения сохраняются.»
85
Глава 6
Упаковки равных шаров.
Покрытия равными шарами
§1. Результаты. Элементарные теоремы
1°. Здесь мы приводим решение для случая плоскости
двух классических задач дискретной геометрии, используя то-
лько понятие L-разбиения и простые теоремы элементарной
геометрии. Использование теорем из главы 5, облегчает полу-
чение результата и несколько уточняет его, обобщая на про-
извольные измерительные тела.
Теорема 6.1. Какова бы ни была упаковка равных от-
крытых кругов на плоскости и какова бы ни была измери-
тельная фигура, плотность (верхняя плотность) упаковки не
может превзойти числа т(yfYl = тг/2 у/З.
Эта плотность при любой измерительной фигуре дости-
гается на "гексагональной" решетчатой упаковке. Рис. 6.01.
86
Теорема 6.2. Каково бы ни было покрытие плоскости
равными замкнутыми кругами и какова бы ни была измери-
тельная фигура, плотность (нижняя плотность) покрытия не
может быть меньше числа 2тг/3у/3.
Эта плотность при любой измерительной фигуре дости-
гается на "гексагональной" решетчатой упаковке. Рис. 6.02.
В доказательствах теорем 6.01 и 6.02 мы фиксируем из-
мерительную фигуру М с центром в точке О (см. главу 5, §2)
и будем рассматривать гомотетичные ей относительно точки
О фигуры AM, где А > 0.
2°. Доказательству мы предпошлем ряд определений и
лемм.
Лемма 1. Для любых о,, (3, > 0, где i = 1,2, ...,N, име-
ют место неравенства:
I //J \ + ft2 + • • • + ОН .
inax(rti//3<) > -----—— > t> •
Pl + Р2 + • • • + PH
87
Лемма 2. Среди треугольников со сторонами a,b,c. >
2г и углами, меньшими Г2(Ь, наименьшую площадь, равную
г2\/3, имеет правильный треугольник Со стороной 2г.
о Пусть Lab- это наибольший из углов рассматриваемого
треугольника, см. рис. 6.03, тогда 120° > Lab > 60°. Имеем
S = sin Lab > 2r2 sin Lab > г2\/з,
где равенства выполнены соответственно лишь при а = Ь = 2г
и cab = 60°.•
Рис. 6.03
Лемма 3. Среди треугольников, вложенных в круг ради-
уса г, наибольшую площадь, равную 3r2v3/4. имеет вписан-
ный правильный треугольник.
6 Пусть некоторый треугольник АВС. вложен в круг ра-
диуса г, имеющий границей окружность С. см. рис. 6.04.а.
Быть может, произведя движение треугольника, мы можем
считать, что А 6 С, а произведя, если нужно, гомотетию в
точке А (и тем самым увеличив плошадь треугольника), мы
88
можем считать, что и еще одна его вершина, скажем В, ле-
жит на окружности. Если и после этого треугольник АВС' не
вписан в окружность С, то продлив отрезок АС- до его пересе-
чения (-' с окружностью, получим треугольник АВС-' боль-
Рис. 6.04
шей площади и уже вписанный в круг. Для этого случая наша
теорема тривиальна, рис. 6.04.Ь.*
§2. Плотнейшая упаковка равных кругов
1°. Определение. Упаковка Т = {ДДТг, • • • .Tfc, • •} по-
парно конгруе.нтных множеств в Е2 называется насыщенной,
если для любого множества Т G Е2 конгруентного 7j сущест-
вует такое множество 7}. с %, что Т П Т* # 0.
Далее, мы предполагаем, что через 27(2) обозначена си-
стема центров расположения Т равных, имеющих радиус г,
кругов на плоскости.
Отметим, что для насыщенной упаковки система £(T)
является системой Делоне.
Лемма 4. Каков бы ни был L-многоугольник в L-разбие-
нии, отвечающем системе Д’('Х), где ‘I произвольная насыщен-
ная упаковка, каждый его угол меньше 120°.
89
t> Предположим противное. Пусть в точке М G S неко-
торый L-многоугольник L] имеет угол М > 120°. Стороны
МР и MQ многоугольника L] имеют длину не меньшую, чем
2г (ведь Е - это система центров упаковки кругов радиуса г).
В силу этих обстоятельств круг, описанный вокруг AMPQ и,
тем самым, вокруг многоугольника L], имеет радиус R > 2г.
Таким образом, мы получили пустой круг радиуса R > 2г,
внутри которого содержится круг радиуса г, не пересекаю-
щийся с кругами упаковки, что в силу насыщенности упаков-
ки Т невозможно.*
Следствие. В условиях леммы 4 L-многоугольниками
могут быть только трех- четырех- и пятиугольники.
о Каждый вписанный zt-угольник при п > 5 имеет по
крайней мере один внутренний угол больший, чем 120°.*
Отметим также, что в условиях леммы 4 ни длина сто-
роны ни длина диагонали L- многоугольника не может превы-
шать 4г, иначе опять мы имеем пустой круг радиуса R > 2г.
Лемма 5. В условиях леммы 4 каждый L-треугольник
пересекается только с теми кругами упаковки, центры кото-
рых расположены в его вершинах.
о Каждая точка системы Е покрыта вместе с окрест-
ностью только "своим" кругом. Поэтому нам достаточно по-
казать, что, в наших условиях, окружность радиуса г. про-
веденная из вершины треугольника, не пересекает противо-
положной ей стороны. Пусть L-треугольник имеет стороны
а, Ь, с, площадь S и радиус описанной окружности R. Вычи-
слим его высоту ha. Имеем abc — 4RS. Отсюда, учитывая,
что R < 2г и а, Ь, с > 2г , получаем
/i„ = 2S/a = bc./2R > b/2. > г.»
Для дальнейшего разобьем каждый четырех- и пятиугольник
L - разбиения его диагоналями, выходящими из какой-нибуд;
одной вершины, на два и три треугольника соответственно.
90
Очевидно, что все сказанное выше об L-треугольниках спра-
ведливо и для треугольников, полученных таким способом.
2°. Доказательство теоремы 6.1. t> Возьмем произ-
вольную упаковку Т кругов радиуса 1, имеющих центрами
точечную систему Z’('I). Если эта упаковка не насыщенная,
то мы дополним ее такими же кругами до насыщенной. Плот-
ность (верхняя плотность) упаковки, какова бы ни была изме-
рительная фигура, от этого не уменьшится, поэтому можем
сразу предполагать, что упаковка 1 насыщенная. Следова-
тельно, мы можем считать систему 17(Т) системой Делоне.
Рис. 6.05
Обозначим через 5тр площадь L-треугольника, через
S’Kp = тг/2 - площадь попавших в него секторов кругов упа-
ковки 1 и через SL сумму по всем Д-треугольникам, пересе-
кающимся с фигурой ХМ. См. рис. 6.05.
91
Обозначим через Ь\м (*£) общую площадь всех кругов упа-
ковки % попавших в фигуру ХМ, деленную на общую площадь
всех треугольников из L-разбиения системы Х’('Г), имеющих
с фигурой ХМ непустое пересечение.
Оценим плотность упаковки. Очевидно, что
^АЛгС^) , ‘^кр/ , \р-
L L
Далее, применив лемму 1, а также одновременно леммы 5 и
2, получаем:
J2*-skp/ ^2 ‘S'Ti’ - »»ах(‘-‘’кр/Л,тр) < = 7г/>/12.
L L
Поскольку граничными эффектами, согласно теореме 5.5 из
гл. 5, можно пренебречь, имеем Лм(Т) < тг/\/Т2.
Правая часть неравенства не зависит от М, имеем
Л(Т) < 7т/VT2.
Поскольку гексагональная упаковка периодична, второе ут-
верждение теоремы очевидно.»
§3 Редчайшее покрытие равными кругами
1°. Лемма 6. Пусть радиус окружности, описанной
вокруг треугольника АВС, не больше, чем г. Пусть так-
же Sa, Sb, Sc секторы кругов радиуса т с центрами в точках
А, В, С, соответственно определенные прямыми АВ и АС. В А
и ВС, С А и СВ. Тогда треугольник АВС' покрыт секторами
S'a, Sb, Sc-
> Для доказательства достаточно рассмотреть три фигу-
ры, см. рис. 6.06, образованные перпендикулярами, опушен-
ными из центра окружности, описанной вокруг треугольни-
ка АВС на его стороны, и половинами ребер треугольника
АВС.»
92
2°. Доказательство теоремы 6.02. t> Возьмем произ-
вольное локально конечное покрытие СТ плоскости Е2 круга-
ми радиуса 1, имеющими центрами точечную систему £(Т).
Тем самым система имеет < 1. Система £(Т)
не имеет предельных точек - иначе покрытие Т не является
локально конечным. Мы будем оценивать плотность в ограни-
ченной области вида ХМ, поэтому в ней для системы Т'(Т)
найдется число ri > 0. Заменив вне области ХМ систему
Е(Т) произвольной системой Делоне, имеющей Rs < 1, мы
получим систему Делоне £ = £\. Для каждой системы £>,
мы можем построить L-разбиение {Д}д. Если Л < /л, то раз-
биения {Ь}д и {L}'t не отличаются внутри области (Л — 1)М.
Только эту часть первого разбиения мы будем в дальнейшем
93
обозначать через {L}a- Подразделив, как и выше, каждый L-
многоугольник на треугольники, мы будем считать {L}a со-
стоящим лишь из треугольников.
Рассмотрим произвольный треугольник Lo G {Ь}а- Его
площадь мы обозначим через 5Тр- Секторы, высекаемые угла-
ми треугольника Ьц из кругов покрытия % имеющих центра-
ми вершины треугольника Lq, согласно лемме 6, покрывают
весь этот треугольник. Через 5кр = тг/2 мы обозначим сумму
площадей этих секторов. Через Sl обозначим сумму по всем
таким треугольникам.
Обозначим через «Тал/С'Х) общую площадь всех кругов по-
крытия 1, имеющих с фигурой АЛ/ непустое пересечение, де-
ленную на общую площадь всех треугольников из {Л}а-
Плотность покрытия оценим, применив леммы 1 и 3:
<7am(*£) > ‘“’кр/ ^тр > min(5Kp/5Tp) >
L L
Л/
Поскольку граничными эффектами, согласно теореме 5.5.
можно пренебречь, имеем > 2тг/3\/3.
Правая часть неравенства не зависит от А/, поэтому име-
ем
4(2) > 2tt/3v/3.
Поскольку гексагональное покрытие периодично, второе ут-
верждение теоремы очевидно.»
§4. О результатах при п > 2
1°. Упаковки. Упаковка равных п-мерных шаров при
п > 1 в «-мерном евклидовом пространстве называется ре-
шетчатой, если центры шаров упаковки образуют решетку
ранга п, в противном случае упаковка называется нерешет-
чатой. Обычно считается, что радиус шара решетчатой упа-
ковки максимален для решетки ее центров.
94
При n = 3 задачу о нахождении плотнейшей, вообще го-
воря, нерешетчатой упаковки поставил Кеплер в 1611 году. В
последние годы появилось несколько работ с доказательством
того, что плотность плотнейшей нерешетчатой упаковки со-
впадает с плотностью плотнейшей решетчатой упаковки. В
части из этих работ найдены ошибки, остальные проверяют-
ся. При ?;. > 10 найдены примеры нерешетчатых упаковок,
имеющих большую плотность, чем у известных решетчатых.
Больше ничего о нерешетчатых упаковках, кроме различного
рода оценок, не известно.
Различными математиками найдены решетки плотней-
ших решетчатых упаковок для п = 2,3,..., 8. Приводим зна-
чения этих плотностей:
п = 2 = 0, 9069... - Лагранж, 1723; Гаусс, 1831;
п = 3 = 0, 7404 ... - Гаусс, 1831;
п = 4 3g — 0,6168... - Коркин и Золотарев, 1872;
71 ~ 5 ТэТг = 0’ 4652... - Коркин и Золотарев, 1877;
п = 6 = 0,3729... - Блихфельдт, 1925;
п = 7 — 0,2952 ... - Блихфельдт, 1926;
п - 8 = 0,2536 ... - Блихфельдт, 1934.
Эти плотности при и — 2,3 достигаются на решетке Л",
которая построена на ребрах правильного n-мерного симплек-
са, выходящих из одной его вершины.
При п = 4 указанная плотность достигается на телесно
центрированной кубической решетке, т.е. решетке, построен-
ной на трех выходящих из одной вершины ребрах 4-мерного
куба и векторе, идущем из той же вершины в его центр.
При п = 5, 6, 7,8 плотнейшие решетки имеют более слож-
ное описание.
95
2°. Покрытия. Покрытие равными n-мерными шара-
ми п-мерного евклидова пространства намывается решетча-
тым, если центры шаров покрытия образуют решетку ран-
га ?i, в противном случае покрытие называется нерешетча-
тым. Обычно считается, что радиус шара решетчатого по-
крытия минимален для решетки ее центров.
Задачу о нахождении редчайшего, вообще говоря, нере-
шетчатого покрытия поставил Кершнер в 1939 году. Однако,
о нерешетчатых покрытиях, кроме теоремы 6.2 и различного
рода оценок, ничего не известно.
Различными математиками найдены решетки редчай-
ших решетчатых покрытий для п = 2, 3,4,5. Приводим зна-
чения этих плотностей:
п — 2
п = 3
п — 4
п - 5
= 1,2(19 ... - Кершнер, 1939;
= 1,464 ... - Бамба, 1954;
= 1, 765 ... - Делоне и Рышков, 1963;
v = 2,124... - Рышков и Барановский, 1975.
Решетки, на которых достигаются эти плотности, суть
решетки Г” взаимные решеткам Г". Плотность покрытия
для решетки Г" дается формулой
Нп
Г п(п + 2)
L 12(?1 + 1)
п + 1.
где через обозначен объем уьмерного шара единичного ра-
диуса.
Известно, что решетка Г" не дает наилучшей плотности
при п = 9 и при всех п > 24. Про остальные размерности
практически ничего не известно.
96