Министерство образования Российской Федерации
Ивановский государственный университет
П.Г. КОНОНЕНКО
ВЫПУКЛЫЕ МНОГОГРАННИКИ
И
РАВНОМЕРНО-ДИСКРЕТНЫЕ СИСТЕМЫ
Иваново
Издательство «Ивановский государственный университет»
2002
УДК
ББК
К
Кононенко П.Г. Выпуклые многогранники и равномерно-дискрет-
ные системы: Учеб, пособие. - Иваново: Иван. гос. ун-т, 2002. - 108 с.
Учебное пособие посвящено разделу евклидовой геометрии, связан-
ному с теорией n-мерных конечногранных выпуклых многогранников
и применению этой теории к дискретной геометрии — нормальным
разбиениям евклидова пространства на области Дирихле-Вороного и L-
многогранники (многогранники Делоне), которые заданы равномерно-
дискретными системами точек пространства. Подробно рассмотрен во-
прос двойственности граней этих разбиений.
Пособие адресовано в первую очередь студентам математического
факультета, специализирующимся на дискретной геометрии, а также
всем, кто интересуется этой тематикой. Требования к подготовке чи-
тателя весьма скромные — это основы линейной алгебры и математи-
ческого анализа.
Печатается по решению редакционно-издательского совета
Ивановского государственного университета
Рецензенты:
кафедра высшей математики
Ивановского государственного химико-технологического университета
кандидат физике математических наук Д.И. Коровин
(Ивановский государственный энергетический университет)
ISBN
© П.Г. Кононенко, 2002
Содержание
Предисловие ............................................. 5
Глава 1. Аффинное евклидово пространство и выпуклые
множества............................................... 7
§ 1.	Аффинная структура евклидова пространства ....... 7
1.	Аффинное евклидово пространство (7). 2. Аффинное подпространство
(плоскость) (8). 3. Аффинная комбинация точек и аффинное подпро-
странство (9). 4. Аффинная оболочка множества (10). 5. Аффинная
независимость точек (12). 6. Аффинный базис подпространства (13).
7.	Уравнения плоскостей. Полупространства (16). 8. Расположение плос-
костей (18). 9. Аффинные отображения пространства (20). 10. Проек-
ция (21). Упражнения (22).
§ 2.	Выпуклые множества ................................... 22
1.	Выпуклое множество (22). 2. Выпуклая комбинация (23). 3. Эквива-
лентное определение выпуклого множества (23). 4. Выпуклая оболочка
множества (24). 5. Теорема Каратеодори (25). 6. Симплекс Sn (25).
Упражнения (26).
§ 3.	Относительная внутренность выпуклых множеств...........27
§ 4.	Внешнее и внутреннее представление замкнутых выпуклых
множеств. Теоремы отделимости. Теорема Минковского . . 31
1. Отделимость выпуклых множеств (31). 2. Крайние точки и теорема
Минковского (34).
Глава 2. Выпуклые многогранники и полиэдральные
множества...................................... 38
§ 1.	Выпуклые многогранники ........................ 38
1.	Выпуклый многогранник (38). 2. Компактность выпуклых много-
гранников (38). 3. Крайние точки. Эквивалентное определение много-
гранников (39). 4. Относительная внутренность выпуклых многогран-
ников (39). 5. Грани выпуклых многогранников (40). 6. Вершины и
крайние точки совпадают (42). 7. Грань является многогранником. Вер-
шины грани (43). 8. Пересечение граней - грань (44).
3
9. Грани граней (45). 10. Минимальная грань содержащая точку мно-
гогранника (47). 11. Многогранник как конечное пересечение полупро-
странств (48). Упражнения (49).
§ 2. Полиэдральные множества .................................. 50
1. Полиэдральное множество. Определение (50). 2. Ограниченные поли-
эдральные множества есть многогранники (52). 3. Грани полиэдральных
множеств (53). 4. Неприводимое представление полиэдрального мно-
жества (55). 5. Представление граней полиэдрального множества (58).
6. Следствия для теории выпуклых многогранников (61). Упражне-
ния (62).
Глава 3. Разбиения пространства Еп, задаваемые равномер-
но-дискретными системами точек............................. 63
§ 1.	Разбиения на многогранники ....................... 63
§ 2.	Равномерно-дискретные системы точек............... 67
§ 3.	Области Дирихле-Вороного точек (г, Я)-систем и разбиение
Дирихле-Вороного ...................................... 69
§ 4.	L-многогранники (многогранники Делоне) (г, Я)-систем и
L-разбиения, задаваемые этими системами................ 79
1.	Метод Б.Н. Делоне ’’пустого шара”. L-многогранник (79). 2. Сте-
пень точки относительно сферы (81). 3. Комментарии к методу ’’пусто-
го шара” (82). 4. Существование L-многогранника (г, Д)-системы (86).
5. Лемма о шапочках пересекающихся шаров (87). 6. Нормальная упа-
ковка L-многогранников. Свойства граней (89). 7. Покрытие простран-
ства L-многогранниками. L-разбиение (95). 8. Необходимые и достаточ-
ные условия для L-разбиения (99).
§ 5.	Двойственность разбиения Дирихле-Вороного и
L-разбиения (разбиения Делоне)........................ 101
Приложение (к главе 3). Центральная проекция................. 106
Список использованной и рекомендуемой литературы ............ 108
4
ПРЕДИСЛОВИЕ
Необходимость написания данного учебного пособия была продик-
тована практикой чтения спецкурсов по дискретной геометрии и вы-
полнения студентами курсовых и дипломных работ на математическом
факультете Ивановского Государственного Универсистета.
Классические работы по дискретной геометрии, такие как исполь-
зуемая здесь работа Б.Н.Делоне ’’Геометрия положительных квадратич-
ных форм” [2] содержат в себе яркие и простые в своей сути геомет-
рические идеи, понимание и использование которых к сожалению, из-за
недостаточной подготовки иногда оказывается или совсем недоступным
для слушателей, или по настоящему остается понятным лишь элемен-
тарный случай размерностей п = 2,3, в то время как обычной практи-
кой является постановка перед студентами задач на исследование гео-
метрических объектов размерности выше трех.
Цель написания данного пособия состояла в том, чтобы дать под-
робное и систематическое введение в раздел геометриии евклидова про-
странства, связанный с выпуклыми многогранниками и разбиениями
пространства на многогранники, заданными равномерно-дискретными
системами точек. Автор везде постарался по возможности сохранить
и наглядность изложения, жертвуя в некоторых случаях общностью, а
также сопровождая длинные и подробные доказательства комментари-
ями и иллюстрациями, облегчающими их понимание.
Пособие состоит из трех глав. Первая посвящена введению в
n-мерную аффинную и евклидову геометрию, основные используемые
понятия которой: плоскости, полупространства, аффинные (барицент-
рические) координаты, свойства выпуклых множеств и теоремы отдели-
мости. Вторая глава содержит введение в теорию выпуклых
n-мерных конечногранных многогранников, где разбираются необходи-
мые далее два основных подхода: многогранник как выпуклая оболоч-
ка вершин и как пересечение полупространств. В этой главе также
подробно разбираются понятия структуры граней многогранника. Тре-
тья глава посвящена равномерно-дискретным точечным системам точек
пространства и заданным ими разбиениями пространства на области
Дирихле-Вороного и многогранники Делоне (L-многогранники).
В тексте систематически используются обозначения:
>	, • — соответственно начало и конец доказательства;
5
>	• — доказательство очевидно;
V	n, Дп, Еп — соответственно линейное векторное, аффинное и ев-
клидово (точечное) пространства размерности п;
s	panMi, affM2, convM^ — соответственно линейная оболочка мно-
жества векторов Mi, аффинная и выпуклая оболочка точечного множес-
тва М2;
S(Q,R), Q(Q,R), O(Q,R) — соответственно n-мерная сфера, замк-
нутый и открытый шар с центром Q и радиусом Я;
F □ G — многогранник F является гранью многогранника G.
Автор выражает глубокую благодарность профессору Е.П. Баранов-
скому за чуткое и внимательное отношение к своей работе, которая из-
начально задумывалась как часть совместного более общего по охвату
учебного пособия, но позднее была выделена в отдельное издание.
Я благодарен профессору С.С. Рышкову и его соавторам Р.Г. Ба-
рыкинскому и Я.В. Кучериненко по книге ’’Решение основных задач
дискретной геометрии в случае плоскости” [9], знакомство с которой
оказалось полезным для меня при написании §4 главы 3 (лемма ”о шаш-
лыке” и другие).
6
Глава 1. АФФИННОЕ ЕВКЛИДОВО ПРОСТРАНСТВО
И ВЫПУКЛЫЕ МНОЖЕСТВА
§ 1.	Аффинная структура евклидова пространства
1.	Аффинное евклидово пространство
Основой всех рассмотрений данного пособия является линейное век-
торное пространство Vn над полем действительных чисел R, имеющее
некоторую конечную размерность п. Используемые далее начальные
понятия этого раздела читатель может найти в обязательном курсе ли-
нейной алгебры, читаемом на математическом факультете, либо в учеб-
никах [6,4,5,8].
Напомним, что n-мерным аффинным пространством, ассоцииро-
ванным с векторным пространством Vn, называется множество Ап
(элементы которого называют точками), снабженное отображением,
ставящим в соответствие любой паре точек (А, В) вектор v Е Vn, обо-
значаемый v = АВ, причем:
1)	отображение La : Ап —> Vn, La : X 1—> АХ (при фиксированной
точке А) — биективно;
2)	для любых точек X, Y, Z Е Ап выполнено соотношение Шаля (прави-
ло треугольника) XY + YZ = XZ.
Векторное пространство Vn называется подстилающим для аффинно-
го пространства Ап. Соотношение v = АВ также записывают в виде
В = А + v и называют трансляцией (параллельным переносом) точки
А Е Ап на вектор v Е Vn.
Начиная с п.7 этого параграфа считаем, что векторное простран-
ство Vn евклидово, то есть снабжено вещественнозначным скалярным
произведением (•, •) (обозначаемым также и точкой •), которое вводится
обычными аксиомами: симметричности ( (ж, у) = (у, х) ), линейности
( (аж1 + /й?2,17) = а(х\,у) + /3(^2,^) ), и положительности скалярного
квадрата ( (Ду Ду ) > О при х ф 0).
Соответственно и аффинное (точечное) пространство Ап становит-
ся евклидовым, приобретая обозначение Еп, которое мы ради единообра-
зия сохраним на протяжении всего пособия (несмотря на то, что пункты
1-6,8 обращены только к аффинным свойствам пространства).
Зафиксировав некоторую произвольную точку О Е Еп (называе-
мую далее началом координат) мы тем самым точкам X, Y,... Е Еп по-
ставим во взаимно однозначное соответствие векторы х = ОХ,
у = ОУ,... G Vn, называемые радиус-векторами этих точек. Из со-
отношений Шаля очевидно следует, что ОУ = ОХ + ХУ, а значит
ХУ = OY - ОХ = у - х.
Отождествление радиус-векторов Т, у,... Е Хп и точек X, У,... Е
Е Еп позволит в дальнейшем на практике ограничиться рассмотрением
элементов Т,у,... векторного пространства Vn, попросту называя их
там, где удобно, точками (X, У,...) и употребляя упрощенные выска-
зывания вида: ’’точка х Е Еп”.
Расстояние между точками вводится обычной формулой:
р(Х,У) := |ХУ| = |у-ж| = -х,у -х).
2.	Аффинное подпространство (плоскость)
(а)	Аффинным подпространством размерности к (—1<к<п) (либо
к-мерной плоскостью) аффинного пространства Еп называют множест-
во А С Еп, для которого (при А 0) существует точка Т Е А такая, что
множество L = {vx = ТХ | X Е Л} представляет собой А:-мерное линей-
ное (векторное) подпространство векторного пространства Vn (также
называемое подстилающим для А). Таким образом А = {Т + v | v Е L}.
Очевидно, что для любых двух точек X, У Е А соединяющий их
вектор ХУ = ТХ — TY = vy — vx лежит в подстилающем вектор-
ном пространстве L. Поэтому такое определение позволяет сразу го-
ворить о том, что А:-мерное аффинное подпространство А само является
аффинным (А:-мерным) пространством, ассоциированным с линейным
пространством L, а также об изоморфизме всех А:-мерных аффинных
пространств.
Пользуясь далее соглашением о векторных обозначениях, получаем
следуещее эквивалентное определение к-мерного аффиного подпростран-
ства (плоскости) А:
(Ь)	А = 0 либо А = t + L, где L — А:-мерное линейное подпро-
странство векторного пространства Vn.
Таким образом, А есть сдвиг (или параллельный перенос) линейно-
го подпространства L на вектор t. Поскольку для любого вектора v Е L
выполнено равенство L = v + L, то для любой точки У Е А выполнено
включение (У — t) Е L и равенство А = t + L = ?+ (й — t) + L = /д +L. То
есть представление аффинного подпространства А не зависит от выбора
точки t Е А. Подчеркнем также, что для любой точки х Е А и вектора
v Е L точка х + v также лежит в А.
Если А ф 0, и v±,..., Vk — какой-нибудь (векторный) базис линей-
ного подпространства L, то А может быть представлено в виде
А = t + «1^1 -h &2V2 + . . . +	«1, «2, • • • , &к £ R (1-1)
(см. рис. 1.1)
Для размерности аффинного подпространства используется обозна-
чение к = dimA. При А = 0 размерность dimA считают равной —1;
0-мерное аффинное подпространство представляет собой, очевидно, точ-
ку; 1-мерное носит название прямой, а (п — 1)-мерное (п - размерность
пространства Еп) называют гиперплоскостью-, наконец А = Еп является
своим n-мерным подпространством.
3.	Аффинная комбинация точек и аффинное подпространство
Аффинной комбинацией точек а±,... ,ат (по аналогии с линейной
комбинацией векторов) называют линейную комбинацию
т	т
^~yXiai = Ai^i + ... + Хтат, в которой Xi = 1.
г=1	г=1
(Буква а рядом со знаком суммы будет дополнительно указывать на то,
что сумма является аффинной комбинацией.)
Аффинная комбинация двух точек х, у, очевидно, всегда может
быть представлена в виде
(1 — Х)х + Ху = х + Х(у — х), А Е R,	(1.2)
а аффинная комбинация любых т точек а±,... ,ат в виде
т	т	т	т
i=l	i=2	i=2	i=2
9
(где £V=1 Xi = 1, а значит Ai = 1 - ^i=2 A;).
Предложение 1.1. Для понятия аффинного подпространства
А С Еп могут быть даны следующие два определения, эквивалентные
определениям (а) и (Ъ). Это множество А С Еп, которое
(с) вместе с любыми двумя точками х,у Е А содержит и любую их
аффинную комбинацию (1.2);
(d) вместе с любыми т точками . ,ат Е А содержит и любую
их аффинную комбинацию (1.3).
> Следствия (Ь)=>(с) и (b)=>(d) очевидны из представлений (1.2) и
(1.3), поскольку х Е А, (у-х) Е L и а± Е А, (а2 — ai),..., (ат — ai) Е L,
где L - векторное подпространство, подстилающее для А. Следствие
(б/) => (с) очевидно. Чтобы доказать следствие (с) => (d), достаточно
представить аффинную комбинацию (1.3) в виде
т	т	m л
= Aiа\ + A;rz; = Ai^i + А ~\ai ">
i=l	i=2	i=2
где A = J2™2Ab откуда Ai + A = 1 и	= 1- (Поскольку
J2™ x = 1? мы без ограничения общности предполагаем, что Ai 1, то
есть А = 52™ 2	0.) Таким образом, выполняется шаг индукции, сво-
дящей аффинную комбинацию т точек к последовательным аффинным
комбинациям (т — 1)-ой и двух точек.
Наконец, чтобы доказать следствие (d) => (6), зафиксируем произ-
вольную точку t Е А и покажем, что множество векторов {x — t | х Е Л}
является векторным подпространством. Действительно, для векторов
Ui = х\ — С V2 =X2~t (xi,X2 Е Л) их линейная комбинация av± + (3v 2 =
= оДтд — F) + (3(х2 — i) = [(1 — а — (5(1 + ах\ + (5х2\ ~i — также вектор из
L, поскольку в квадратных скобках стоит аффинная комбинация точек
из А. •
Упражнение 1.1. Докажите, что если точки ... ,ат выражают
в виде аффинной комбинации каждую из точек Б1,...,Б^, а те в свою
очередь аффинно выражают точку с, то точки ..., ат также аффинно
выражают точку с.
4. Аффинная оболочка множества
Из определения (с) легко видеть, что пересечение любого семейства
аффинных подпространств (плоскостей) есть снова аффинное подпро-
странство. Поэтому (по аналогии с линейной оболочкой spanV множес-
тва векторов V) естественным образом вводится следующее понятие.
Аффинной оболочкой множества точек М С Еп, либо аффинным
подпространством, натянутым на М (обозначается affM), называют
наименьшее аффинное подпространство, содержащее множество М.
(То есть affM С А для любого аффинного подпространства А, содер-
жащего М.) Таким образом, affM совпадает с пересечением всех аф-
финных подпространств, содержащих М (одно из которых - само про-
странство Еп).
Размерностью множества М называют размерность аффинного
подпространства affM, натянутого на М (обозначается
dimM := dim(affMf).
Предложение 1.2. Аффинная оболочка affM произвольного под-
множества М С Еп совпадает с множеством
т
i=l
всевозможных (конечных) аффинных комбинаций точек из М.
> Докажем, пользуясь (с), что К - аффинное подпространство, что
будет означать включение К D affM. Действительно, любые две аф-
т	_ к _
финные комбинации точек из М а = ^2аХ{Сц, b = ^aXjbj (52™ х Xi =
г=1	j=l
— ^kj=v P'j = 1) можно расширить (слагаемыми с нулевыми коэффици-
ентами) до аффинных комбинаций одних и тех же точек {ci,... ,ср} =
= {ai.... ,ато} U {&1,... ,Ьк} следующего вида а = ^aXiCi, b =
i=l	i=l
Тогда аффинная комбинация точек а и b имеет вид (1 — а)а + ab =
р	р	р
= (1 — ci) ^2aXiCi + a	= 52а[(1 — ot)Xi + ащ] • Ci и есть снова
i=l	i=l	i=l
точка из К, поскольку J2f=1[(l — ci)A^ + арч\ = 1.
С другой стороны, affM, являясь аффинным подпространством,
вместе с любыми точками di,...,am из М в силу (d) содержит и все
их аффинные комбинации. То есть К С affM. •
Замечание. Операция взятия аффинной оболочки сохраняет вклю-
чения. То есть для любых множеств Mi, М2 С Еп включение Mi С М2
влечет включение affM± С affM2-
11
5.	Аффинная независимость точек
(al) Точки ai,...,am Е Еп называются аффинно независимыми
(иногда употребляют термин линейно независимы), если не существу-
ет ненулевого набора чисел од,..., ат с суммой
(1-4)
В противном случае точки . ,ат называются аффинно (либо линей-
но) зависимыми.
Предложение 1.3. Аффинная независимость точек . ,ат эк-
вивалентна каждому из следующих утверждений:
(Ь1) Векторы АкА± = аг - ак,..., АкАк_г = ак_г -ак,АкАк+1 =
= ак+\ — ак,... ,АкАт = ат — ак (проведенные из любой точки Ак во
все оставшиеся из Ai,..., AmJ — линейно независимы.
(cl) Никакая из точек , ат не является аффинной комбина-
цией остальных.
> Эквивалентность определения (al) и условия (bl) следует из сле-
дующих равенств (для ^2™ х од = 0)-
т	т	ттт
Т	) &к Т	&к)
i = 1
i^k
Для доказательства следствия (cl) => (al) предположим, что точки
ai,... ,ат аффинно зависимы и в соотношении (1.4) од 0. (С точнос-
тью до перенумерации это гарантировано определением (al).) Тогда
соотношения (1.4) после переноса слагаемых од и в правую часть
ЕТП
i=2 (А эквивалентны соотношениям
т	т
и, после переобозначений /щ = —оц/а^ (i = 2,... ,т), соотношениям
= ai,
i=2
Е i: = 1-
i=2
Для доказательства обратного следствия достаточно положить //i = — 1,
перенеся ai в последнем равенстве в левую часть. •
6.	Аффинный базис подпространства
Учитывая равносильность независимости т векторов и (т + 1) точ-
ки (в предложении 1.3) далее удобно нумеровать точки, начиная с нуля.
Аффинным (говорят также барицентрическим) базисом аффинного
подпространства А С Еп называют аффинно независимую систему то-
чек ао,... ,ak Е А таких, что любая точка х Е А может быть представ-
лена как аффинная комбинация
к	к
x = '^Xiai	(УА = 1)	t1,5)
2=0	2=0
точек ао,...,
Замечание. Представление (1.5) любой точки х Е А единственно,
к	к	к	к
>	Действительно, если х = 52 xt6i = 52 Угбч xi — 52 ЗА = 1) —
2=0	2=0	2=0	2=0
два аффинных представления точки х, то 0 = х — х = 52^=о(жг— ЗаЖ, гДе
52i=o(x* — У г) = 0- Из аффинной независимости точек ао,... ,ak следует,
что Xi - yi = 0 (г = 1,..., к). •
Вернемся к определению аффинной оболочки affM для подмно-
жества М С Еп. Набор аффинно независимых точек ао,...,ат Е М
называется максимальной аффинно независимой системой точек мно-
жества М, если добавление к системе любой точки а Е М делает ее
аффинно зависимой.
Вопрос о существовании для подпространства affM аффинного ба-
зиса, составленного из точек множества М, и размерности этого аффин-
ного подпространства решается следующим предложением.
Предложение 1.4. Пусть М С Еп и к = dim(affM), и L - под-
стилающее линейное векторное подпространство для affM. Тогда для
аффинно независимой системы точек ао, - - - ,ат Е М справедливо нера-
венство т < к, и эквивалентны следующие условия:
(а2) ао, - - - ,ат - максимальная аффинно независимая система то-
чек из М.
(Ъ2) ао, - - - ,ат - аффинный базис подпространства affM.
(с2) affM = aff{a0, .. ,ат}.
(d2) векторы ё± := (ai — ао), ..., ёт := (am — ао) составляют (век-
торный) базис линейного подпространства L;
(е2) т = к;
>	Обозначим А аффинную оболочку множества М. Поскольку по
условию предложения система точек ао,... ,ат аффинно независима,
условия (Ь2) и (с2) по сути означают возможность аффинного выраже-
ния любой точки у Е а = affM через ао,... ,ат, и потому эквивалент-
ны.
Чтобы доказать следствие (а2)=>(Ь2)(с2), добавим к аффинно неза-
висимой системе точек ао,- - - ,ат Е М еще одну точку х из множества
М. Тогда найдутся числа До,, Хт, А Е R такие, что
т	т
i=Q	i=Q
Очевидно, что А 0 (иначе система точек ао,... ,ат была бы аффинно
зависимой). После перенесения слагаемого Хх в правую часть и деления
на —А, как и в предложении 1.3, получаем аффинное разложение точки
х по точкам ао,..., ат.
Таким образом, любая точка xi Е М допускает аффинное разло-
жение по точкам ао, • • • ,ат. В свою очередь, любая точка у Е affM
допускает (конечное) аффинное разложение по точкам xi Е М (предло-
жение 1.2), а значит (см. упражнение 1.1) и по точкам ао,... ,ат.
Импликация (Ь2)=>(а2) следует из предложения 1.3, поскольку до-
бавление к аффинному базису ао,---,ат аффинного подпространства
affM любой точки х Е М С affM делает систему аффинно зависимой
в силу возможности разложения х по аффинному базису.
Заметим теперь, что векторы ё± = (ai — ао),---,ёт = (ат — ао)
линейно независимы (предл. 1.4) и лежат в А:-мерном линейном подпро-
странстве L (см. рис. 1.2). Поэтому т < к, и только при т = к они
являются (векторным) базисом в L (то есть (d2)o(e2)).
Для доказательства эквивалентности (b2)o(d2) осталось показать,
что возможность аффинного разложения любой точки х плоскости А
по аффинному базису ао,... ,ат эквивалентна возможности линейного
разложения любого вектора v из линейного подпространства L по (век-
торному) базису ё\,...,ёт (см. рис. 1.2).
14
Действительно ((62) <= (с2)), любая точка х G А может быть пред-
ставлена как х = ао + v (где v := х — ао Е L), а вектор v - линейно
разложен по векторному базису
'Г — А1С1 Ч- ... Ч- Amem.
Тогда (учитывая, что et = at — ао, г = 1,..., m)
.т = ао + г =
т
Т А^е^
г=1
и обозначая Aq = 1 — 52Zti А^, получаем аффинное разложение
т	т
x = '^2aXiai ( У2 А» = 1\
г=0	г=0
(1-7)
И наоборот ((62) => (с2)), любой вектор v Е L может быть пред-
ставлен в виде v = х — ао (где х := ао + v Е Л); точка х аффинно
разложена по формуле (1.7), и (двигаясь налево по выше написанной це-
почке равенств) вектор v = х — ао - линейно разложен по формуле (1.6).
•
Пример. Аффинная оболочка двух различных точек То,Ti Е Еп
представляет собой множество af/{Tq,Ti} = {(1 — а)хо + qTi} и явля-
ется 1-мерным аффинным подпространством, то есть прямой.
Следствие. Любая система ао, •.. ,ар линейно независимых точек
из множества М может быть дополнена до аффинного базиса подпро-
странства affM.
15
>	Если первоначальная система точек не является максимальной,
следует добавлять по одной точке aq Е М с сохранением аффинной не-
зависимости до тех пор пока она не станет максимальной. •
Из этого предложения, в частности, следует, что любая система
аффинно независимых точек ао,... ,ат (т < п) может быть дополнена
до аффинного базиса ао,... ,ап пространства Еп. И любая точка х Е Еп
допускает единственное аффинное разложение
г=0
г=0
по этому базису. Однозначно определенные числовые коэффициенты
х°,хг,... ,хп называют аффинными (либо барицентрическими) коорди-
натами точки х относительно аффинного базиса ао,... ,ап. (Номера ко-
ординат хг принято ставить сверху.)
Из рассмотрения равенств (1.6), (1.7) легко видеть, что числа
хг,...,хп являются также (обычными) координатами радиус-вектора
АоХ = х — ао относительно (векторного) базиса
Ci — AqAi — а± ао, . . ., еп — АоАп — ап ао,
(1-8)
’’прикрепленного” к начальной точке Aq.
7.	Уравнения плоскостей. Полупространства
Возвращаясь к вопросу о представлении аффинных А:-мерных под-
пространств (плоскостей), введем (векторный) базис ё1,ё2,... ,ёп в про-
странстве Еп, ’’закрепленный” в начале координат О. Тогда радиус-
вектор любой точки X может быть разложен по базису
(1-9)
где х1, х2,..., хп — координаты точки х.
Из представления (1.1) очевидно, что полное решение совместной
неоднородной линейной системы (относительно координат ж1,... ,хп)
Ьцх1 + &12Ж2 + ... + ь1пхп = С1,
(1.Ю)
16
имеющей ранг г = (п — к), представляет собой А:-мерную плоскость вида
(1.1), где t = (х1,...,хп) - частное решение неоднородной системы, а
= (^,...,5	, Vk —	-	~ Фундаментальное решение одно-
родной системы. Несложно доказать, что и всякое представление плос-
кости (1.1) является решением некоторой системы вида (1.10). Действи-
тельно, для нахождения коэффициентов bij (г = 1,..., п — к, j = 1,..., п)
следует найти фундаментальное решение однородной системы ранга к
bl Vj + ... + briv'‘ = 0 (j = 1,..., к)
(относительно неизвестных &i,...,6n). А затем положить Cj = bj^x1 +
+ ... + bjnxn (j = !,...,&).
В частности, любая гиперплоскость Н может быть задана уравне-
нием
Н : Ь^х1 +	+ ... + Ьпхп = с	(1-11)
(коротко Ьт • х = с, где Ь, х - вектор-столбцы). Или, если использовать
скалярное произведение, то в виде
п
Н :	(д,ж) = с (или эквивалентно а^дгх^ = с),
i,j=l
где с G R, д = (д1,..., дп) - вектор нормали к гиперплоскости К, связан-
ный с системой чисел bj соотношениями bj = аг19г (j = 1, • • • , ^), в
котором aij =	- ej (1 < г, J < п) - элементы матрицы Грама для базиса
^1 , • • • , •
Неравенства
(д, х) < с, (д,х) > с (соответственно (д, х) < с, (д,х) > с)
задают открытые полупространства Н~,Н+ (соответственно замкну-
тые полупространства Н_,Н+), ограниченные плоскостью Н. Свойст-
ва открытости и замкнутости полупространств следуют из того, что
Н~,Н+ и Н.Н+ являются полными праобразами соответственно от-
крытых и замкнутых лучей на прямой R при отображении х хк
(ставящем в соответствие точке х ее А:-ую координату хк) либо отобра-
жения х (р,ж), которые являются непрерывными функциями точки
х. (Непрерывность может быть доказана, например, переходом к ор-
тонормированному базису и соответственно применением неравенства
Коши-Буняковского (р,ж) < \д\ • |ж|).
Перейдем к аффинным координатам, положив Aq = О (ао = 0) и
введя аффинный базис ао,*й, • • • , ап соотношениями (1.8), что соответ-
ствует лишь присоединению координаты х° = 1 — х1 — ... — хп к коор-
динатам (ж1,...,^71) радиус-вектора х произвольной точки X. Любое
линейное однородное уравнение в аффинных координатах
Ло^° + h\xr + ... + hnxn = 0	(1-12)
после исключения переменной eZ/   1 eZ/	• • • eZ/ п преобразуется к
виду
(hi - /го)®1 + • • • + (hn - ho)xn = с,
то есть к виду (1.11), где наборы чисел ho, hi,... ,hn и c,bi,... ,bn свя-
заны взаимно однозначными преобразованиями
с = -ho, bj = hj - ho (j = 1,..., n)
ho = -c,	hj =bj — c (j = 1,..., ri).
Итак, уравнения гиперплоскостей H в аффинных координатах имеют
вид (1.12). А соответствующие строгие [нестрогие] неравенства задают
открытые [замкнутые] полупространства Н~,Н+ [Н~.Н+].
8.	Расположение плоскостей
Пусть Ai, Л-2 - непустые плоскости (аффинные подпространства)
в евклидовом пространстве Еп, ассоциированные с линейными вектор-
ными подпространствами Li,Z/2 соответственно. То есть А± = ti + Li,
Л-2 = ?2 + ^2. Пересечение плоскостей А = А± А Л.2, которое, как замече-
но выше, также является плоскостью, очевидно, либо пустое множество
(Л = 0), либо имеет вид А = £q + Zz, где L = L± AL2 - линейное векторное
подпространство, полученное пересечением, а /д произвольная точка
из А. (Проверьте это!)
Полезно иметь в виду, что условие L± + L2 = Vn является доста-
точным, (хотя и вовсе не необходимым) для непустоты пересечения
плоскостей Ai и А^ (Ai А А^ 0). (Докажите это самостоятельно, ис-
пользуя то, что любой вектор х^ — %i для х^ Е А2, Xi Е Ai может быть
разложен в сумму 77i + ^2, где 77i Е L1/V2 Е Z/2-)
Плоскости Ai и А2 называются дополнительными, когда подстила-
ющие линейные пространства Li,Z/2 дополнительны (то есть
Li А L2 = {0}, Li + Z/2 = Vn). В этом случае очевидно, что пересечение
Ai А А2 = {ж} — всегда представляет собой единственную точку. (До-
кажите это!) И, в частности, это справедливо, когда плоскости ортого-
нальны (обозначение Ai±A2), то есть когда линейные подпространства
Li,Z/2 ортогонально дополнительны (Li = L% это означает (iJi,^) = 0
6 L1,V2 £ L/2^-
Примером дополнительных (ортогональных) аффинных подпрост-
ранств на плоскости Е2 могут служить любые две пересекающиеся (со-
ответственно ортогональные) прямые, а в Е3 - пересекающиеся (орто-
гональные) прямая и плоскость.
Плоскости Ai и Д2 называются параллельными (обозначение
А1||А2), если для подстилающих линейных подпространств справедливо
включение L± С Ь2 или L± Э Очевидно, что в случае параллельности
пересечение плоскостей есть либо пустое множество (Ai А А2 =0), либо
одна из плоскостей Ai, Д2 (Ai при Li С L2- А2 при Li D L2). (Докажи-
те! Проверьте соответствие ’’обычным” определениям параллельности
прямых и плоскостей в Е2 и Е3.)
Рассмотрим теперь взаимное расположение произвольной собствен-
ной А:-мерной плоскости Ак (0 < к < п — 1) и гиперплоскости Нп~г
(dim,Hn-[ = п — 1), ассоциированных с линейными подпространствами
Ед и L7^1 соответственно. Очевидно, что условие параллельности в
этом случае примет вид лишь одного включения С L7^1 (посколь-
ку Г// С La влечет Ь#-1 = L\). Пусть также - одно из двух
замкнутых полупространств, ограниченных гиперплоскостью Нп~г.
Возможны следующие ситуации:
1)	Ак\\Нп~\ тогда возможно:
а)	плоскости не пересекаются (Ак А Нп~г = 0), и тогда либо
AA' Q я™-1 — 0, либо Ак С Я™-1 (рис. 1.3 а,б);
б)	плоскость Ак лежит в плоскости Яп 1 {Ак С Нп ’). и тогда,
очевидно, Ак С (рис. 1.3 в).
2)	Ак Нп[ (то есть	и	= Vn). Известная теорема
алгебры о размерности пересечения и суммы линейных подпространств
в этом случае утверждает:
dim(LkA ALJ-1) = dimLkA + dimL7^1 — dim(LkA + L^-1) = k + (n — 1) — n =
а)	б)	в)	г)
Рис. 1.3
= к — 1. Таким образом пересечение плоскостей Ак и Нп~г пред-
ставляет собой (к — 1)-мерную плоскость Нк~г = АкГ\Нп~1 - гиперплос-
кость в аффинном пространстве Ак. А пересечение Ак АН™-1 плоскости
Ак с полупространством К™-1 (в Еп) представляет собой полупростран-
ство (в подпространстве Ак) (рис. 1.3 г).
(Докажите это. Для этого: введите локальный базис ё'15... ,ё'к Е ЬкА
и локальные координаты хг',...,хк' в плоскости Ак, выразите через
них глобальные координаты (1.9), и подставьте в неравенство, соответ-
ствующее равенству (1.11).)
И наоборот, любая гиперплоскость Нк~г в подпространстве Ак мо-
жет быть получена пересечением Нк~г = Нп~г А Ак некоторой гипер-
плоскости Нп~г (в Еп) с подпространством Ак, а соответствующее по-
лупространство — пересечением	А Ак.
Действительно, если Hk~r = t + span{e±,...,ё^-i}, то векторный
базис ё1,...,ё^_1 в Lk^r может быть последовательно дополнен до ба-
зиса в ЬкА и Vn векторами и ... ,ёп. Тогда
Hn~r = t + span{ei,... ,ё^_1,ё^+1,... ,ёп} (где spanV - линейная обо-
лочка или линейное подпространство, натянутое на векторы множества
V).
9.	Аффинные отображения пространства
Напомним, что линейным называют отображение £ : Vn —> V*5, со-
храняющее любые линейные комбинации двух векторов:	+/ЗТ2) =
= а • £(Ti) + (3 • £(^2) (Wl, V2 Е Vn, q, (3 Е R). А следовательно £ сохра-
няет и любые линейные комбинации из т векторов, для т > 2.
Отображение р : Еп —> Efe называют аффинным. если оно сохраня-
ет любые аффинные комбинации двух точек, то есть </?((! — А)Т + Ху) =
20
= (1 - A)  <p(x) + A  ip(y) (\/x,y 6 E”,A 6 R). Легко видеть, что аф-
финные отображения сохраняют и любые аффинные комбинации из т
точек, для т > 2 (см., например, доказательство предложения 1.1):
т	т	т
<р (52°А^)= У?а(гЭе ХВ = х) •
i=l	i=l	i=l
При любой фиксированной точке xq пространства Еп любую точку
х Е Еп можно представить в виде х = xq + v (и тогда v = х — х$).
Предложение 1.5. Отображение <р : Еп —> Efe является аффин-
ным, если и только если его можно представить в виде
<p(x)=ip(x0+v')=y0 + £(v'),	(1.13)
где £ : V” —> V* - линейное отображение соответствующих линейных
векторных подстилающих пространств (и, очевидно, у0 = ip(xo)).
> Следует лишь проверить сохранение аффинной комбинации для
отображения <^(г), и линейной комбинации для £(v) = ip(xo + v) — у0,
пользуясь связью между аффинными и линейными комбинациями по
типу формулы (1.3). •
Соотношения (1.13) можно записать в виде р(х) = <^(#o) +£(ж — xq).
И если обозначить а = <^(#o) — то ip преобретает вид
р(х) = а + £(ж).
10.	Проекция
Пусть Z/i,Z/2 - Два дополнительных линейных векторных подпро-
странства векторного пространства Vn (чьи размерности удовлетворя-
ют равенству dimLi -EdimL^ = п), относительно которых Vn разлагает-
ся в прямую сумму Vn = Li В £2- То есть любой вектор v Е Nn может
быть однозначно разложен в сумму v = 77i + 7725 Ti Е V2 Е
Линейной проекцией вдоль подпространства L± на подпространство
L2 называется линейное отображение П : Vn —> L2, действующее по
правилу П : v = v± + v% 1—> V2>
Пусть теперь А1,Л.2 - две дополнительные плоскости, ассоцииро-
ванные с дополнительными линейными подпространствами Li,Z/2, и пе-
ресекающиеся в единственной точке {жд} = Ai А А2.
Аффинной проекцией вдоль подпространства на подпространство
Аз называют аффинное отображение тг : Еп —> Аз, определенное по
правилу
7г(ж) = Xq + П(ж — Xq)
7г(ж) = 7г(жо + V) = Xq + П(??)-
Упражнения
1)	Докажите, что линейная проекция П(ж) и аффинная проекция
7г(ж) являются соответственно линейным и аффинным отображениями.
2)	Покажите, что аффинная проекция тг(ж) может быть определена
следующим образом. Через любую точку х Е Еп следует провести плос-
кость А^, ассоциированную с линейным подпространством Li (то есть
И тогда 7г(ж) - это единственная точка пересечения дополни-
тельных плоскостей А^ и Аз (тг(ж) := А^ П Аз). Выведите отсюда, что
проекция 7г(ж) не зависит от выбора точки xq Е A3.
§ 2. Выпуклые множества
1.	Выпуклое множество
(а	) Множество М С Еп называют выпуклым, если вместе с любыми
точками х,у Е М оно содержит и весь отрезок \х, у]:
[х,у\ :={(! — а)х + ay | а Е [0,1]}
Примеры: 1) А:-мерная плоскость А (0 < к < п) вместе с любыми
двумя своими точками жд, xi содержит и прямую aff{xo,xi}, которая
включает отрезок [х,у], а, значит, является выпуклым множеством.
2)	Открытые и замкнутые полупространства Н~,Н+ и Н_,Н+, огра-
ниченные гиперплоскостью К, выпуклы. Действительно, если Н~ за-
дана неравенством (относительно переменной ж) (р,ж) < с, то для лю-
бых точек жо,Ж1 из Н~ выполнено (р,жд) < с, (g,#i) < с, а, значит,
для всякой точки г = (1 — а)х$ + ах\ Е [жд, #1] выполнено (g,z) =
= (1 — а)(д,хо) + a(g,xi) < (1 — <т)с + ас = с. То есть z Е Н . Для
остальных случаев доказательства аналогичны с учетом замены стро-
гих неравенств на нестрогие для замкнутых полупространств.
3)	Объединение Н~ U Н+ двух противоположных открытых полупро-
странств, ограниченных гиперплоскостью К, не является выпуклым
множеством. Действительно, если жд Е Н~, х± Е Н+ и (р,жд) = со < О,
(g, Ti) = ci >0, то найдется число а такое, что (1 — а)с$ + ас\ = 0. И
тогда для точки z = (1 — а)х$ + ах\ Е [жд, #1] справедливо равенство
(д, ж) = (1 — <т)со + ас\ = 0. То есть ~z Е Н и z Н~ U Н+.
2.	Выпуклая комбинация
Выпуклой комбинацией гп точек ,..., ат называют сумму
т	т
x = '^2cXiai, где ^2 Aj = 1 и Ai > 0,..., Ато > 0.	(2.1)
г=1	г=1
(Буква ” с” рядом со знаком суммы дополнительно указывает на то,
что сумма является выпуклой комбинацией.) Таким образом, это аф-
финная комбинация, на которую наложено условие неотрицательности
числовых коэффициентов.
Очевидно, что выпуклая комбинация двух точек Т, у всегда имеет
вид
(1 — а)х + ау, где 1 — а > 0, а > 0, то есть а Е [0,1].
3.	Эквивалентное определение выпуклого множества
Из следующего равенства легко видеть, что выпуклую комбинацию
т точек (ш > 3) можно представить как последовательные выпуклые
комбинации (ш — 1)-ой и двух точек.
т	т	m л
= Aiа\ + XiOi = Aiа\ + А ^~^с—Qj 5
i=l	i=2	i=2
23
где Ег=1 А; = 1, А; > 0 (г = 1,..., m). Причем Ai ф 1 и А =	-=2 Аг > О,
откуда Ai + А = 1 и ^2™ 2	= 1- Поэтому следующее определение (Ь)
эквивалентно определению (а).
(Ь) Множество М С Еп называют выпуклым, если вместе с любыми
точками . ,ат Е М оно содержит и любые их выпуклые комбина-
ции (2.1).
4.	Выпуклая оболочка множества
Легко проверить, что пересечение любого семейства выпуклых мно-
жеств — выпукло. Поэтому корректно следующее определение.
Выпуклой оболочкой множества М С Еп (обозначается convM) на-
зывают наименьшее выпуклое множество, содержащее М (то есть
convM С V для любого выпуклого множества V, содержащего М). Та-
ким образом, convM есть пересечение всех выпуклых множеств, содер-
жащих М (одно из которых есть само пространство Еп).
Предложение 2.1. Выпуклая оболочка convM произвольного мно-
жества М С Еп представляет собой множество
т	т
i=l	i=l
всевозможных (конечных) выпуклых комбинаций точек из М.
> Доказательство почти дословно повторяет доказательство пред-
ложения 1.2 § 1 этой главы с учетом присоединения условия А^ > О
(г =	•
Замечание. Легко видеть, что операция взятия выпуклой оболоч-
ки сохраняет включения, то есть для любых множеств Mi, М2 С Еп
включение Mi С М2 влечет convMy С convM^.
Пример 1. Выпуклая оболочка любых двух различных точек х, у
представляет собой множество conv{x$,x\} = {z = (1 — o)xq +	| A E
E [0,1]}, являющееся отрезком [xqMi]-
Пример 2. Выпуклая оболочка т точек ..., Ат, лежащих на
плоскости Е2 представляет собой многоугольник Р2, ограниченный ло-
маной, которую можно наглядно представить, если обмотать натянутой
резиновой нитью гвозди, ’’вбитые в плоскость Е2” в точках А\,..., Ат
(см.рис. 2.1). Причем лишь некоторые из этих точек являются верши-
нами многоугольника Р2, огороженного этой нитью. (Строгие доказа-
тельства см. в гл.2.)
24
Рис. 2.1
4
Рис. 2.2
Пример 3. Выпуклая оболочка т точек А±,..., Ат, расположен-
ных в 3-мерном пространстве Е3 представляет собой многогранник Р3,
ограниченный поверхностью тонкой резиновой пленочки, натянутой на
неподвижные точки Ai,..., Ат (см. рис. 2.2). Причем лишь некоторые
из этих точек являются вершинами многогранника Р3.
5.	Теорема Каратеодори
Из предложения 1.4 § 1 следует, что при взятии аффинной оболочки
affM множества М можно ограничиться аффинными комбинациями
одного аффинно независимого набора (базиса в affM).
Предложение 2.2 (теорема Каратеодори). При взятии выпук-
лой оболочки (2.2) можно ограничиться лишь выпуклыми комбинациями
всевозможных аффинно независимых наборов ai,... ,ат точек из М.
> Покажем, что если точка х представлена как выпуклая комбина-
ция (2.1) аффинно зависимых точек ai,... ,am, то одну из точек можно
исключить из этого представления. Пусть ^2™ х Да* = 0, где ^2™ х Д =
= 0. Положим /ti = Xi — t/3i (для некоторого t Е R). Тогда
т	т
х =	=	(2.з)
г=1	г=1
Потребуем теперь, чтобы рц = X; — Pf >0 (г = 1,... ,т) и равенство
достигалось бы хотя бы для одного номера i = l,...,m. Для этого
следует положить t = min{Xi//3i | Д > 0}. Таким образом (2.3) -
требуемое представление. •
6.	Симплекс Sn
Пусть точки Aq, ..., Ап с радиус-векторами ао,...,ап составляют
аффинно независимую систему в n-мерном пространстве Еп, то есть
являются аффинным базисом. Тогда их выпуклая оболочка
х = xlai | хг = 1, хг > 0(г = 0,..., п)
г=1	г=1
(2-4)
называется п-мерным симплексом. Заметим, что представление каж-
дой точки х G S как выпуклой комбинации (2.4) единственно. (И как
будет видно далее, это единственный случай, когда вся выпуклая обо-
лочка множества М представляется как выпуклые комбинации одного
аффинно независимого набора.)
Таким образом, симплекс S есть множество точек х, аффинные ко-
ординаты (ж0, х1,..., хп) которых (относительно ао,... ,ап) удовлетво-
ряют системе неравенств
х° > 0, х1 > 0,..., хп > О
Другими словами, S является пересечением (n-hl)-oro замкнутого полу-
пространства хк > 0 (к = 0,1,..., п), то есть S - замкнутое множество.
Аналогичные рассуждения показывают, что подмножество S° С S,
удовлетворяющее системе неравенств х° > 0, х1 > 0,..., хп > 0 - откры-
то и непусто, поскольку содержит, например, точку
хс =	(центр масс симплекса), аффинные координаты ко-
торой (^-,..., ^pi)« Итак, intS D S° 0. На самом деле справедливо
равенство intS = S°, поскольку каждая точка х = (ж0,..., хп) Е S, хотя
бы одна из координат которой равна нулю (хк = 0), является граничной
для полупространства хк > 0, а, следовательно, и для симплекса S.
Заметим, что тем самым теорема Каратеодори утверждает, что вы-
пуклая оболочка множества М является объединением всевозможных
симплексов Sk (к = 0,1,..., п) с вершинами в точках из М.
Упражнения
1) Пусть р — аффинное отображение пространств Еп —> Ет. До-
кажите следующие утверждения.
да) Если множество U выпукло в Еп, то его образ cp(U) является
выпуклым в Ет. Полный праобраз	выпуклого в Ет множества
V является выпуклым в Еп.
(б) Для любого множества М С Еп справедливо равенство
ip(conv М) = conv{cp(JM)}.
(в) Пусть {ao,ai,... ,ап} — аффинный базис пространства Еп, оп-
ределяющий аффинные координаты (Т/ , Т/ , • • • , Т/ ") (ELA =	т°-
чек пространства Еп. А П+ — полупространство, заданное неравенст-
вом х° > 0. Покажите, что образ	при аффинном отображении
есть либо ^-плоскость Ак = aff< <р(ао,..., ап)} (0 < к
пространство в подпространстве Ак, ограниченное (к — 1)-плоскостью
Hk~r = aff< <p(aiA • • • ?	Выведите отсюда, что образ лю-
бого полупространства П+ С Еп есть либо А:-мерная плоскость Ак С Еш
(0 < к < ш), либо полуплоскость в Ак.
< п) либо полу-
§ 3. Относительная внутренность выпуклых множеств
Понятие относительной внутренности является обобщением поня-
тия внутренности на случай, когда приходится иметь дело с набором
выпуклых множеств различных размерностей, например, граней вы-
пуклых многограников. К примеру, внутренность треугольника Т =
= cotiv{xq, Ж1, Х2} и отрезка [жд, #1] в трехмерном пространстве Е3 пус-
та, в то время как относительная внутренность представляет собой со-
ответственно треугольник без границ и интервал (То, Тд).
Т = СОПУ{Хл, х2}
а)
I = COnv{X0, Xj}
*0
б)
Рис. 3.1
Точка х из множества М С Еп называется относительно внутрен-
ней в М, если х является внутренней для М в подпространстве affM
(А:-мерной плоскости, 0 < к < п), являющемся аффинной оболочкой мно-
жества М. Другими словами, х содержится в М вместе с некоторым
А:-мерным открытым шаром Ок(х, г) с центром в точке х и радиусом
г > 0, расположенным в А:-мерной плоскости affM (см. рис 3.1 а,б).
Множество относительно внутренних точек множества М назы-
вается его относительной внутренностью и обозначается riM. Итак
riM = intaffMM, где гп£дМ - внутренность множества М в подпро-
странстве А. Очевидно, что для М С Еп равенство riM = intM спра-
ведливо только в случае, когда dimM = п.
Теорема 3.1 Для любого выпуклого множества М его относитель-
ная внутренность непуста (riM 7^ 0/
>	Пусть dimM = dirnfaffM) = к (0 < к < п). Согласно предло-
жению 1.4 § 1 этой главы среди точек множества М можно выбрать
аффинный базис ао,а±,... ,ak А:-мерного пространства affM.
Из предложения 1.1 § 2 этой главы очевидно, что множество М
вместе с точками ао,а±,... ,ak Е М содержит и их выпуклую оболочку
— А:-мерный симплекс Sk = conv{a$,..., Как показывает пример
из § 2 и соображение об изоморфизме всех А:-мерных аффинных про-
странств, симплекс Sk содержит непустую (А:-мерную) внутренность
int(affM)$k 7^ 0 в А:-мерном пространстве affM. Причем очевидно, что
int(affM)Sk Q int^ffM^M = riM. Итак, riM 0. •
Относительной границей выпуклого множества М С Еп называют
множество rbM = clM \ riM (где с1М - замыкание множества М).
Очевидно, что rbM = дМ (дМ = clM \ intM - обычная граница
множества М) только в случае, когда dimM = п. Если же dimM < п,
то дМ = М f rbM, так как riM 0. Отметим, что понятия относи-
тельного замыкания не вводится, поскольку замыкание множества М
в плоскости affM совпадает с замыканием в Еп в силу замкнутости
множества affM.
Следующая теорема утверждает, что из относительно внутренней
точки выпуклого множества можно ’’увидеть” любую его граничную
точку через слой относительно внутренних точек.
Теорема 3.2. Если М С Еп - выпуклое множество, и xq Е riM,
у Е clM, то полуинтервал [^o,F)	riM.
(где [х0,У) = {(1 - А)ж0 + Ху | А е [0,1)}.)
>	Итак, пусть к := dimM = dimfaffM). Доказательство ведется
в два этапа. Пусть сначала у Е М. Покажем, что произвольная точка
z\ = (1 — Х)у + Ажо (для произвольного фиксированного А Е (0,1]) из
а)	б)
Рис. 3.2
полуинтервала (?/, жд] лежит в riM.
Возьмем А:-мерный открытый шар О^(жо,г) с центром в точке жд,
целиком лежащий в М С affM (см. рис. 3.2 а). (Он существует,
поскольку xq Е riM = intaffMM.) Нетрудно доказать, что в результате
гомотетии с центром у и коэфициентом А шар Ok(xQ,r) переходит в шар
Ok(zx, Ar) = (1 - Х)у + ХОк(х0,г)
(поскольку для любой точки z = (1 — Х)у + Аж, х Е Ok(xQ,r) выполнено
z —~z\ = [(1 —А)?/ + Аж] — [(1 —А)?/ + Ажо] = А(ж — xq) и \z — z\\ = |А|• \х — жо|).
Всякая точка z = (1 — Х)у + Хх из шара Ok(z\, Ar) (х Е Ok(xQ,rf)
принадлежит отрезку [у,х], лежащему в М (в силу выпуклости мно-
жества М). Таким образом, весь шар О^(гл,Аг) лежит в М и z\ Е
Е riM.
На втором этапе предположим, что у Е clM \ М. Пусть снова z\ =
= (1 — А)?/ + Ажо, А Е (0,1). Тогда у =	Теперь гомотетия с
центром в точке z\ и коэффициентом — ^у преобразует А:-мерный шар
Ok(xQ,r) в А:-мерный шар
(лежащий в affMf который содержит хотя бы одну точку w из мно-
жества М (поскольку у Е clM). Тогда легко видеть, что найдется точ-
ка х Е Ok(xQ,r) такая, что z\ = (1 — A)w + Хх (достаточно положить
х = у^А — ^y^w). Таким образом, w Е М, х Е riM, z\ Е (ffx)
следовательно, ~z\ лежит в riM вместе с интервалом (w, х). •
29
Следующее предложение говорит об устойчивости свойства вы-
пуклости по отношению к операциям замыкания и относительной внут-
ренности.
Предложение 3.3. Относительная внутренность riM и замыка-
ние с1М произвольного выпуклого множества М С Еп - выпуклы.
> 1) Для любых точек х,у Е riM в силу теоремы 3.2 справедливо
[Т, т/] С riM.
2)	Если точки х,у Е clM, то существуют последовательности точек
{Т/.}, {^} Е М (возможно стационарные), имеющие своим пределом
точки х и у соответственно. Тогда любая точка z\ = (1-А) х + Ху
(А Е [0,1]) является пределом последовательности точек
= (1 — X)xk + Xyk (k = 1,2,...), лежащих (в силу выпуклости) в
множестве М. Таким образом z\ Е с1М. •
Предложение 3.4. Для произвольного выпуклого множества
М С Еп справедливы соотношения:
1)	affM = afffriM) = aff(clM);
2)	clM = cl(riM) = cl(clM);
3)	riM = ri(riM) = ri(clM);
4)	rbM = rbfriM) = rb(clM);
5)	dimM = dim(riM) = dim(clM).
> Пусть k = dimM.
1)	а) С одной стороны riM С M => afffriM) C affM, а с другой
в riM можно найти А:-мерный шар, в котором можно выбрать (k + 1)
аффинно независимую точку ао,... ,ак, являющуюся базисом в affM.
Поэтому affM = aff{a0, ...,ак} С aff(riM).
б)	Из замкнутости affM следует, что М С clM С affM и
отсюда affM С aff(clM) С affM.
2)	Так как М D riM, то clM D cl(riM). Для любой точки у Е clM
возьмем То Е riM, тогда (Д, То] С riM => у Е cl(riM).
3)	а) гг(ггМ) = intaff^iM^intaffMM) = intaffM(intaffMM) =
= intaffMM = riM.
б)	M С clM => riM С ri(clM). С другой стороны VT Е ri(clM)
возьмем То Е riM. Тогда отрезок [Т, То] можно продлить в clM за точку
Т. То есть Зу Е clM : х Е (jy, То] С riM.
4)	rb(riM) = clfriM) \ rifriM) = clM \ riM = rbM,
rb(clM) = cl(clM) \ ri(clM) = clM \ riM = rbM.
5)	Очевидно из пункта 1. •
30
§ 4.	Внешнее и внутреннее представление
замкнутых выпуклых множеств.
Теоремы отделимости. Теорема Минковского
1.	Отделимость выпуклых множеств
Множества Mi, М2 С Еп называются соответственно а) отдели-
мыми, б) строго отделимыми, в) сильно отделимыми, если существует
гиперплоскость Н, удовлетворяющая соответствующим условиям: а)
Mi и М2 принадлежат противоположным замкнутым полупространст-
вам Н+,Н~, ограниченным Н, б) хотя бы одно из множеств Mi, М2
принадлежат открытому пространству Н~ или Н+, а другое - противо-
положному (замкнутому), в) Mi и М2 принадлежат противоположным
открытым полупространствам Н~,Н+.
Несмотря на то, что справедлива общая теорема об отделимости лю-
бых двух выпуклых множеств, не имеющих общих относительно внут-
ренних точек, мы позволим себе ограничиться лишь ее частными слу-
чаями.
Лемма 4.1. Для любого открытого выпуклого множества U и не
принадлежащей ему точки xq найдется строго отделяющая их гипер-
плоскость Н, проходящая через xq (то есть U принадлежит одному из
открытых полупространств, ограниченных Н) (см. рис. 4-1 а)-
> Проведем доказательство индукцией по размерности п. При п = 1
утверждение очевидно. Докажем его для п = 2. Вокруг точки xq опи-
шем окружность S = S(xq, 1) радиуса г = 1 (см. рис. 4.1 б). Произведем
центральную проекцию р с центром xq множества U на окружность S,
поставив каждой точке у G U в соответствие точку у' - пересечение лу-
ча [жо,?7[ и окружности S. Множество p(W) на окружности S - связно и
открыто (в силу открытости и связности L7), то есть представляет собой
интервал, центральный угол а между концами которого удовлетворяет
неравенству а < тг. (В противном случае на окружности S найдутся
диаметрально противоположные точки и xq Е U, что не так.) Прямая /,
проведенная через xq и один из концов этого интервала, и есть искомая
отделяющая гиперплоскость.
Предположим теперь, что утверждение леммы справедливо для раз-
мерностей к < п — 1 и докажем его для к = п > 2. Через точку xq U
проведем гиперплоскость <тп-1, имеющую непустое пересечение с мно-
жеством U (см. рис. 4.1 в). (Если U Е\ап~г = 0, то все доказано.) Тогда
согласно предположению индукции в ап~г существует гиперплоскость
Нп~2 Э Xq, отделяющая множество L7n-1 = U А а (являющееся вы-
пуклым и открытым в ап-1). Рассмотрим проекцию тг множества U
вдоль плоскости Нп~2 на двумерную плоскость у2, перпендикулярную
плоскости Нп~2.
Очевидно, что 7г(То) = тг(Нп-2) тг(?7), а множество тг(1Г) - откры-
то и выпукло. Поэтому найдется прямая /, содержащая точку 7г(То) и
строго отделяющая множество ir(U). Легко видеть, что (п — ^-плос-
кость Н = af f{Hn~2,/} = tt-1(Z) не пересекается с множеством U и
является искомой отделяющей плоскостью. •
Рис. 4.2
Гиперплоскость Н и соответственно ограниченное им замкнутое
полупространство К (равное Н или Н+) называются опорными к мно-
жеству М С Еп в точке xq Е М, если М С К и xq Е Н (см. рис. 4.2
а,б). Если к тому же М Н (то есть М A intK 0), то гиперплос-
кость Н и соответственно замкнутое полупространство К называются
собственно опорными (рис. 4.2 б).
Заметим, что Н отделяет точку xq и множество М. Таким образом
можно сказать, что множество G находится целиком по одну сторону
плоскости Н и своей точкой xq ’’опирается” на плоскость К.
Предложение 4.2. Если полупространство К (и ограничивающая
его гиперплоскость Н) являются собственно опорными для выпуклого
множества М, то riM С intK (и соответственно riM А Н = $).
>	Обозначим k = dimM = dim(af fM), Н+ = К, а Н - противо-
положное (открытое) полупространство. Возьмем произвольную точку
xq Е riM (riM 0 по теореме 3.1), и точку у Е intK А М 0. Предпо-
ложив, что xq Е Н, заключаем, что xq лежит в М вместе с открытым
А:-мерным шаром 0^(То,г), а потому отрезок [у, То] (который как и шар
Ok(xQ,r) лежит в А:-мерной плоскости affM^ может быть продлен в
множестве М за точку xq в полупространство Н~, что невозможно,
так как М С Н+. •
Далее в этом параграфе мы будем оперировать лишь замкнутыми
выпуклыми множествами.
Теорема 4.3. Для любого замкнутого выпуклого множества
G С Еп и любой его относительно граничной точки xq Е rbG сущест-
вует собственная опорная гиперплоскость Н к множеству G в точке
Xq.
>	Пусть А = affG - подпространство, являющееся аффинной обо-
лочкой множества G, и k = dim(af fG) (см. рис. 4.3). Очевидно, что
xq riG = MaG. В силу выпуклости множества riG (предложение
3.3) и леммы 4.1 в А:-мерном подпространстве А найдется гиперплос-
кость Нк~\ содержащая xq и строго отделяющая множество riG. Пусть
множество riG принадлежит открытому полупространству тогда
G С Нк+ \ то есть Нк~х является собственно опорной гиперплоскостью
для G (в подпространстве А). Очевидно, что плоскость Hk~r С А мож-
но дополнить до (п — 1)-плоскости Н в Еп такой, что Н А А = Нк~г.
Легко видеть, что тогда Н является искомой собственной опорной ги-
перплоскостью в пространстве Еп для множества G в точке xq. •
33
Замечание. Из доказательства теоремы легко видеть, что
dim(H A G) < dimG — 1 < dimG.
Предложение 4.4. Для любого выпуклого замкнутого множества
G и не принадлежащей ему точки х найдется:
1) опорная гиперплоскость Н к G (в некоторой точке xq Е G),
строго отделяющая х и G. (То есть xq принадлежит одному из откры-
тых полупространств Н.Н+, a G - противоположному замкнутому.)
2) гиперплоскость Н' Э х, параллельная Н и строго отделяющая х
и G.
> Если х Е affG, возьмем произвольно у0 Е riG (см. рис. 4.4 а). На
интервале (Т,у0) найдется точка xq, граничная для G, через которую
можно провести собственную опорную гиперплоскость Н такую, что
G С Н+, G Н. Тогда у0 принадлежит открытому полупространству
Н+. Поэтому х Е Н~ (иначе х Е Н и точка xq вместе с интервалом
(Т,у0) по теореме 3.2 принадлежала бы Н+, что неверно).
В случае, когда х affG = А, плоскость affG можно дополнить
до гиперплоскости Н D affG, Н х, которая и будет искомой опорной
строго отделяющей гиперплоскостью (см. рис. 4.4 б). Существование
Н' в обоих случаях очевидно. •
Предложение 4.5. Любое замкнутое выпуклое множество можно
представить как пересечение всевозможных его опорных
полупространств. > •
2. Крайние точки и теорема Минковского
Точка х замкнутого выпуклого множества G С Еп называется
крайней, если не существует интервала с концами в точках множест-
ва G, содержащего точку х. Множество всех крайних точек замкнутого
выпуклого множества G обозначается extG.
Легко видеть, что точка х из замкнутого выпуклого множества G
является крайней в том и только том случае, когда множество
G\{T} выпукло. И в частности крайняя точка х множества G не может
являтся выпуклой комбинацией других точек из G (поскольку в этом
случае G \ {ж} не выпукло).
Легко также видеть, что всякая крайняя точка х Е extG является
для множества G относительно граничной (х Е rbG = G\riG), посколь-
ку любая относительно внутренняя точка х$ Е riG входит в G вместе
с некоторым А:-мерным шаром Ок(хо,г) (при к = dimG > 1), а значит
и вместе с некоторым интервалом (у, г) Э xq с концами у, z Е G.
Примеры. 1) Если G = {ж} - одноточечное множество, то
extG = {ж}. 2) Крайние точки отрезка [Tq,Ti] есть в точности его
концы: ext[xQ,x±] = {Tq,Ti}. 3) Крайние точки многоугольников и
пространственнх многогранников есть в точности их вершины (дока-
зательство для произвольной размерности см. в гл. 2). 4) Множество
крайних точек замкнутого круга есть ограничивающая его окружность,
а для замкнутого шара - ограничивающая его сфера (см. следствие
предложения 4.6).
Предложение 4.6. Если Н - опорная гиперплоскость к замкну-
тому выпуклому множеству G, то ext(G А Н) = (extG) А Н, то есть
крайними точками множества G А Н являются в точности крайние
точки G, попавшие в гиперплоскость Н.
> Если х Е extG, то G\{T} - выпукло => (GC\H)\{x} = (G\{x})C\H
- выпукло. То есть ext(G А Н) D (extG) А Н. С другой, стороны пусть
х Е ext(G А Н), и пусть G лежит в замкнутом полупространстве Н+.
Для любой пары точек у, г из G возможны случаи: 1) у, г Е Н. тог-
да х (у, г); 2) хотя бы одна из точек у, г принадлежит открытому
полупространству Н+ (теорема 3.2), тогда интервал (у, z) С Н+ и, сле-
довательно, х (у, z). •
Следствие. Если точка х замкнутого выпуклого множества G мо-
жет быть получена пересечением {ж} = GC\H множества G с его опор-
ной гиперплоскостью Н, то х - крайняя точка множества G. (Коротко:
Теорема 4.7. (Минковского) Пусть G - компактное (т.е. замк-
нутое и ограниченное) выпуклое множество в En, а V - подмножество
в G. Тогда следующие условия равносильны:
(a)	G = conv{V};
(b)	extG С V.
И, в частности, G = conv(extG), то есть G является выпуклой обо-
лочкой своих крайних точек.
> Докажем импликацию (а) => (Ь) от противного. Предположим,
что найдется точка х Е extG, х V, то есть V С G \ {ж}. Однако
G\ {ж} выпукло, и потому convV CG \ {ж}, что противоречит условию
convV = G.
Чтобы доказать импликацию (Ь) => (а), достаточно доказать соот-
ношение G С conv(extG). Действительно, обратное включение очевид-
но, поскольку G D extG и G выпукло. А соотношение extG С V С G
в этом случае влечет G = conv(extG) С convV С convG = G, то есть
convV = G.
Рис. 4.5
Доказательство включения G С conv(extG) будем вести по индук-
ции размерности к множества G. При к = 0 и к = 1 компактное выпук-
лое множество G является соответственно точкой и отрезком, и утверж-
дение очевидно (см. примеры 1,2). Для к > 2 возьмем произвольную
точку х Е G. Если х принадлежит относительной границе G, то по тео-
реме 4.2 через х может быть проведена опорная плоскость Н. Но тогда
множество G' = GC\H - выпукло и компактно (как ограниченное пере-
сечение выпуклых замкнутых множеств), и dimG' < dimG — 1, а значит
для х применимо предположение индукции. То есть х является выпук-
лой комбинацией крайних точек множества G' = G А Н. являющихся
36
(согласно предложению 4.6) и крайними точками множества G.
В случае, когда х Е riG, через точку х поведем произвольную пря-
мую I (см. рис. 4.5). В силу компактности и выпуклости множества
G пересечение I A G является отрезком [у, z] Э х, где у, z - относитель-
но граничные точки множества G. Рассуждая как и выше, видим, что
точки у и г являются выпуклыми комбинациями некоторых крайних то-
чек ^i,... ,ук и!1,... ,zm, множества G, а х в свою очередь выпуклой
комбинацией точек у, г. Таким образом х есть выпуклая комбинация
крайних точек уг,... ,ук, zi,... ,zm множества G (см. упр.1 § 1 гл.1). •
Глава 2. ВЫПУКЛЫЕ МНОГОГРАННИКИ
И ПОЛИЭДРАЛЬНЫЕ МНОЖЕСТВА
§ 1.	Выпуклые многогранники
1.	Выпуклый многогранник
(а) Множество Р С Еп называют выпуклым многогранником. если
Р представимо как выпуклая оболочка конечного множества точек (см.
рис. 2.1, 2.2 § 2 гл. 1):
Р = com?{wi, w2,..., wm}.	(1.1)
Замечание. Выпуклая оболочка и размерность многогранника Р
определяется точками из формулы (1.1): affP = aff{w±,..., wm},
dimP = dim{wi,..., wm}.
> Действительно, любая выпуклая комбинация является и аффин-
ной комбинацией, а потому {wi,...,wm} С Р = conv{w±,..., wm} С
С aff{wi,..., wm} (см. предложения 1.2 и 2.2). Отсюда
aff{wi,. •• ,wm} С affP С aff{wi,..., wm}. •
2.	Компактность выпуклых многогранников
Теорема 1.1. Любой выпуклый многогранник Р является выпук-
лым компактным (замкнутым и ограниченным) множеством в Еп.
> Пусть Р = conv{w±,..., wm}. Выпуклость Р очевидна. Что-
бы доказать компактность, возьмем произвольную последовательность
точек из множества Р и покажем, что из нее можно выбрать
подпоследовательность, сходящуюся к некоторой точке xq из Р. Дейст-
вительно, каждая из точек х^ 6 Р представима как выпуклая комбина-
ция вида xk = X[wi + ... + A™wm (А*. + ... А™ = 1; А*. > 0,..., А™ > О,
к = 1,2,...). Таким образом, определены т числовых последователь-
ностей {А^}^?=1,...,	, точки которых лежат в компактном мно-
жестве - отрезке [0,1]. Поэтому из последовательности {А^}^ТХ можно
выбрать подпоследовательность {AJ.	сходящуюся к числу
Xq Е [0,1]. А из соответствующей подпоследовательности {А^}^ТХ
можно еще раз выбрать подпоследовательность {А^, сходящуюся
к числу Aq Е [0,1]. Переходя таким образом последовательно т раз
к подпоследовательностям, получим т числовых последовательностей
{А^}^2=1,..., {А^}^, сходящихся к числам Aq, ..., А^ из отрезка [0,1],
причем Aj + ... + Xq1 = 1 (поскольку A^ + ... + A)™ = 1, r = 1,2,...).
Соответствующая подпоследовательность точек x^r = Aj. Wi + AJ?wm,
(r = 1,2,...), очевидно, сходится к точке х$ = Ajwi + ... + Aq'w/;).
принадлежащей многограннику Р = сопх{йр,..., wm}, поскольку по-
следнее представление является выпуклой комбинацией. •
3.	Крайние точки. Эквивалентное определение многогранников
Из последней теоремы и теоремы Минковского (4.5) следует, что в
определении (1.1) многогранника Р множество {wi,...,wm} содержит
все крайние точки Р ({w,..., wm} D extP = {?7i,... vr}). Причем
P = conv{v^ .. .vr}.	(1.2)
Некоторые из точек wi,..., wm могут оказаться лишними, принадлежа
выпуклой оболочке остальных. Множество же крайних точек extP =
= {?7i,... vr} является минимальным набором, выпуклая оболочка ко-
торого образует многогранник Р (см. рис. 2.1, 2.2 § 2 гл. 1). Из
сказанного (и теоремы Минковского) очевидно, что понятию выпукло-
го многогранника можно дать следующее эквивалентное определение.
(Ь) Выпуклый многогранник - это выпуклое компактное множество
в Еп, обладающее конечным множеством крайних точек.
4.	Относительная внутренность выпуклых многогранников
Предложение 1.2. Относительная внутренность riP выпуклого
многогранника Р (1.2) с крайними точками extP =	пред-
ставляет собой множество
/у»	/у»
PW =	= 7? Ат | 72 = 1; Ai > 0,..., Хг > 0}	(1.3)
г=1	г=1
всевозможных выпуклых комбинаций всех крайних точек со строго по-
ложительными коэффициентами.
> Заметим, что в п.6 § 2 гл.1 предложение уже доказано для частно-
го случая, когда крайние точки представляют собой систему из (n + 1)
аффинно независимой точки, а Р есть n-симплекс. Причем очевидно,
это единственный случай, когда разложение (1.3) точек х единственно.
В остальных случаях необходимо доказать лишь существование требу-
емого разложения.
Докажем включение riP D Р^. Пусть размерность многогранника
dimP = dim{vi,... ,vr} = к. Будем считать (возможно после перенуме-
39
рации), что первые (к+1) крайние точки 771,...,77^+i (к+1 < Г) аффинно
независимы (см. предложение 1.4). А их выпуклая оболочка образу-
ет А:-мерный симплекс Sk. имеющий непустую А:-мерную внутренность
в многограннике Р. Тогда для любой точки х е справедливо
X = ^2cXiVi = а(	+ @( Ес +>i) = ау0 + /Зу^ где у0,у± -
i=l	' i=l '	' i=k-\-2	'
к-\-1	г
точки, описанные в круглых скобках, а = xi > 0, /3 =	> О,
1=1	г=к+2
и, очевидно, а + (3 = 1. Таким образом, х е [?7о> 3/1), а Ун £ г^к
У\ 6 Р. И по теореме 3.2 х Е riP (см. рис. 1.1 а).
а)	б)
Рис. 1.1
Для доказательства включения riP С Р^ возьмем произвольную
точку х Е riP. Возьмем также точку у{} =	+ ... + Е Р (см.
рис. 1.1 б). Поскольку х Е riP, отрезок [7/0,ж] можно продлить в
множестве Р за точку х до полуинтервала [у, г) Э Т, (где z Е Р и
г
z = ^2cXiVi, ELiXi =	=	Тогда найдется число
i=l
г
а Е [0,1] такое, что х = (1 — а)у + az = J2C[(1 — а) - + аА^]^. Коэф-
i=l
фициенты этой выпуклой комбинации строго положительны, а потому
х Е	•
5.	Грани выпуклых многогранников
Подмножество F n-мерного многогранника Р С Еп называется его
гранью размерности к (0 < к < п) или к-гранъю (обозначение F □ Р),
если существует опорная гиперплоскость Н, отсекающая множество F,
то есть F = Н А Р и dimF = к (см. рис. 1.2 а). Пустое множество
и сам многогранник Р так же считают гранями размерностей — 1 и п
40
соответственно, называя их несобственными гранями в отличие от выше
описанных собственных граней.
Грани размерности dimP — 1 = (п — 1) называют гипергранямщ
1-грани — ребрами, а 0-грани — вершинами. Для множества всех
А:-граней многогранника Р , будем использовать обозначение Рр(Р).
Рис. 1.2
Замечание. В случае, когда размерность многогранника Р равна
m < п, и Ат = affP - m-мерное аффинное подпространство, натянутое
на Р, для определения грани следует, конечно, брать опорную гипер-
плоскость в подпространстве Ат (см. рис. 1.2 б). Однако всегда
найдется гиперплоскость Нп~г в Еп такая, что = Ат А Нп~г.
И наоборот, любая опорная к Р гиперплоскость Нп~г (в Еп) либо со-
держит подпространство Ат (и многогранник Р), либо пересекает Ат
по гиперплоскости = Нп~г А Ат (в Ат), опорной к Р. Поэтому
данное выше определение грани без изменений можно распостранить на
случай dimP = т < п.
Примеры. 1) Грани, ребра и вершины трехмерного выпуклого мно-
гогранника, очевидно, можно отсечь 2-мерными плоскостями. 2) Реб-
ра и вершины плоского многоугольника, расположенного в трехмерном
пространстве (ш = 2 < 3 = п) также можно отсечь 2-мерными плоскос-
тями (см. рис. 1.2 а,б).
На самом деле легко видеть, что любая А:-мерная грань F может
быть отсечена от многогранника Р своей аффинной оболочкой, то есть
представлена пересечением F = Р А Ак многогранника Р и А:-мерной
плоскости Ак = affF, лежащей вместе с гранью F в опорной плоскос-
ти Н. отсекающей грань F. (Проверьте это (!), используя очевидные
включения F С affF С К.)
41
6.	Вершины и крайние точки совпадают
Заметим, что для любой грани F выпуклого многогранника Р мно-
жество P\F выпукло. Действительно, если F получается пересечением
F = Р А Н многогранника Р с опорной гиперплоскостью Н. соответ-
ствующей опорному замкнутому полупространству Н+, то Р \ F =
= Р \ Н = Р А Н+ (поскольку Р С 7?+), где Н+ - соответствующее
открытое полупространство. Множество P\F является выпуклым как
пересечение выпуклых множеств Р и Н+. В частности любая вершина
(0-грань) х определяет выпуклое множество Р\{Т}, а значит х является
крайней точкой множества Р. На самом деле справедлива теорема.
Рис. 1.3
Теорема 1.3. Для любого выпуклого многогранника Р множество
его вершин (0-граней) и множество крайних точек совпадают (коротко
^(0) = extP).
> Включение 7-р(0) С extP доказано. Чтобы доказать включение
7-р(0) D extP, возьмем произвольную крайнюю точку 77i Е extP =
=	• • • -Р-} (возможно после перенумерации). Точка 771 не яв-
ляется выпуклой комбинацией других крайних точек (см. замечания
к определению § 4), и потому не принадлежит выпуклому компакту
conv{v2,..., vr}. Согласно следствию 4.3 теоремы отделимости через
вершину 771 можно провести гиперплоскость Н с уравнением (х, п) = а,
строго отделяющую множество conv(extP \ 771). Таким образом, одно
из открытых полупространств Н~, Н+ (пусть Н~) содержит множество
extP \ {Т1}, все точки щ которого удовлетворяют строгому неравенст-
ву (77^, п) < а (г = 2,...,г), a (77i,n) = а. Очевидно, что любая точка
х многогранника Р может быть разложена в выпуклую комбинацию
крайних точек х = Ai77i + ... + Xrvr (Xi = 1, Xi > 0). Поэтому
(T, n) = Ai (77i, n) + ... + Ar(77r, n) < (Ai +... Xr)a = а, причем равенство
достигается лишь в случае, когда А2 = ... = Хг = 0, и, следовательно,
42
Ai = 1, что соответствует точке х = 771. Таким образом, гиперплоскость
Н отсекает точку TJi: Р А Н = {Ti}, и, следовательно, TJi — вершина
многогранника Р. •
7.	Грань является многогранником. Вершины грани
Теорема 1.4. Для любой к-грани F (0 < к < п) выпуклого много-
гранника Р справедливы утверждения:
1)	F - компактное выпуклое множество:
2)	extF = (extP) A F;
3)	F является выпуклым многогранником размерности к;
4)	affF = aff(extF), dimF = dim(extF) = к.
> 1) Пусть F образовано пересечением F = Н А Р опорной гипер-
плоскости Н с многогранником Р. Оно выпукло и компактно, поскольку
Н и Р выпуклы и замкнуты, а Р еще и ограничено.
2) extF = ext(P A Н) = (extP) А Н = (extP) А (Н А Р). Крайние точки
грани F - это крайние точки пересечения Р А Н. По предложению 4.4
гл. 2 это крайние точки (вершины) многогранника Р, попавшие в опор-
ную гиперплоскость Н. то есть попавшие и в грань Р.
3) Поскольку extF С extP, очевидно F есть выпуклый компакт с конеч-
ным числом крайних точек — многогранник. 4) Очевидно из замечания
к определению Р. •
Подчеркнем еще раз, п.2),3) утверждают, что вершины грани F -
это в точности вершины многогранника Р, попавшие в Р. И Р - их
выпуклая оболочка.
Следствие 1. Гиперплоскость Н отсекает грань F = Н А Р вы-
пуклого многогранника Р в том и только том случае, когда Н является
опорной для множества вершин extP. (То есть все вершины располо-
жены по одну сторону от Н и хотя бы одна - в ней самой.) В этом
случае вершины грани F - это в точности вершины многогранника Р,
попавшие в гиперплоскость Н, и сама грань F - их выпуклая оболочка
(см. рис. 1.2 а,б).
> Действительно, если гиперплоскость Н и замкнутое полупрост-
ранство Н+ являются опорными для множества вершин extP, то
extP С Р+, extP АН 0 => Р = conv(extP) С Н+, Р А Н 0,
поскольку Н+ - выпуклое множество.
Обратно, если Н и Н+ - опорные для многогранника Р, то есть
Р С Н+, РГН ф 0, то extP CPC Н+. Предположив, что extPC\H = 0,
получаем, что extP С Н+ - открытое полупространство), и тогда
Р = conv(extP) С #+, что неверно. •
Таким образом, грани многогранника Р при помощи операции вы-
пуклой оболочки отождествляются с подмножествами множества вер-
шин extP = {771,..., vr}. Однако следует понимать, что не все такие
подмножества определяют грань. Например подмножества, определяю-
щие гиперграни удовлетворяют критерию следующего следствия (для
А:-мерных граней (0 < к < п) см. упражнения в конце параграфа).
Следствие 2. Подмножество М =	вершин п-мерного
выпуклого многогранника Р, имеющее размерность dim М = п — 1 опре-
деляет гипергранъ F многогранника Р, равную его выпуклой оболочке
F = сопи М в том и только том случае, когда проведенная через него
гиперплоскость Н = aff М является опорной для полного множества
вершин многогранника Р (см. следствие 1).
Пример. В квадрате conv{v±, Т?2, 77з, Т4} подмножества вершин
{771,77з} и {772,774} не определяют грани (ребра), поскольку проведенная
через них прямые I1J2 не является опорными для множества вершин
(имеются вершины, расположенные по разные стороны прямой).
Следствие 3. Множество всех граней (размерностей
к = 0,1,..., dimP) любого выпуклого многогранника Р конечно.
8.	Пересечение граней - грань
Теорема 1.5. Пересечение F = Fi любого числа граней выпук-
лого многогранника Р есть снова его грань.
> Очевидно, что достаточно рассмотреть лишь пересечения конеч-
ного числа граней. А метод математической индукции позволяет свес-
ти вопрос к пересечению двух граней. Случай несобственных граней
очевиден. Итак, пусть F = F± A F^, где F±,F2 - грани, полученные
пересечениями F± = Р А F^ = Р А Т?2- Здесь Н\.Н2 - опорные ги-
перплоскости к многограннику Р, заданные уравнениями (ж,п±) = од,
(ж,П2) = «2 (см. рис. 1.4). Соответствующие опорные замкнутые полу-
пространства Ну заданы неравенствами (ж, 771) < од, (ж, Й2) < «2-
Образуем гиперплоскость Н с уравнением (ж, 77) = а, где
п = 77i+7i2, а = «1 + «2- Тогда для любой точки у G Р справед-
ливо (7/, 77) = (^,771 + 772) = (^,771) + (т/, 772) < сц + а2 = а. То есть
(7/, 77) < <+ и равенство достигается лишь в случае, когда (7/,77i) = од,
(у,П2) = «2- Значит, точка у G Р лежит в гиперплоскости Н лишь
44
тогда, когда она лежит в обеих плоскостях Н\.Н). Поэтому Р Г\ Н =
= (Р A Hi) А (Р А Н>) = Pi А Р2 = F — грань многогранника Р. •
9.	Грани граней
Поскольку по утверждению теоремы 1.4 любая грань F многогран-
ника Р также является многогранником, имеет смысл говорить о гранях
грани F.
Теорема 1.6. Для любого выпуклого многогранника Р, любой его
грани F и подмножества G грани F (G С F □ Р) следующие условия
равносильны:
a)	G - грань грани F;
b)	G - грань многогранника Р.
> Чтобы доказать импликацию (Ь) => (а), будем считать, что
F = Нр А Р, G = На А Р, где Н/.Н(; - опорные гиперплоскости к
многограннику Р (см. рис. 1.5 а). Случаи G = F и G = 0 очевидны.
Будем считать, что G F и G 0. Таким образом пересечение плос-
костей Н = Hf А На непусто и Н С Нр (собственное подмножество).
Поэтому dimH = (п — 1) — 1 = п — 2 (далее Н = Нп~2). Итак (поскольку
G С F С HF) G = HGHP = HGnHF ПР = Нп~2 А Р, причем Нп~2 -
опорная гиперплоскость к множеству F в подпространстве Нр (так как
F С Р С Н@, а значит F С На А Нр = (Рп-2)+ - полупространство в
Нр). Поэтому G - грань многогранника Р.
Пусть теперь GAPAPhP= Нр~г АР, G = Нп~2 АР, где Р^-1 -
опорная (п — 1)-плоскость к Р, Нп~2 - (п — 2)-плоскость, расположенная
в Нп~г и опорная к Р. Задача состоит в том, чтобы образовать опорную
45
к Р (п — 1)-плоскость Н^Г , чтобы она отсекала грань G = Н^Г1 А Р.
Для этого следует ’’слегка повернуть” плоскость Нр~г вокруг плоскости
у^-п-2 „от Грани” р, не доходя до касания с остальными вершинами
многогранника Р (см. рис. 1.5 б).
Действительно, пусть уравнение плоскости есть (ж, пр) — &F?
а Нп~2 задается системой из этого уравнения и уравнения (ж, п) = а
(вектор п лежит в плоскости Нр и перпендикулярен пр - нормали к
плоскости Р[р~г) (см. рис. 1.5 б).
Считаем, что вершины многогранника Р удовлетворяют неравен-
ству (Т, пр) < ар, а все вершины грани F еще и неравенству (ж, п) < а.
Причем в первом случае равенство достигается только на вершинах гра-
ни F, а во втором - только на вершинах грани G.
Для некоторого е > 0 образуем плоскость Н£, заданную уравнением
(Т, п£) = а£, где п£ = пр + ёп, а£ = ар + еа. Заметим, что для любой
вершины v многогранника Р справедливо
(у, п£) = (у,пр + еп) = (1?, пр) + е(у, п).
(1-4)
Рассмотрим расположение всех вершин многогранника Р относительно
плоскости Н£. Напомним, что extG С extF С extP.
1)	Вершины v грани G лежат в плоскости Н£, поскольку v Е Нр~\
v Е Нп~2, а, следовательно, (у, п£) = ар + га = а£ (см. (1.4)).
2)	Вершины v грани F, не лежащие в G, лежат в плоскости Я^-1,
но не лежат в Яп_2, то есть (у, пр) = ар, (у,п) < а, откуда (у, п£) <
< ар + еа и поэтому v Н£ (у Е Ну).
3)	Вершины многогранника Р, не лежащие в F, удовлетворяют
строгому неравенству (у, пр) < ар', а потому неравенство (у, п£) < а£
справедливо для них при е = 0. Оно останется справедливым и при до-
статочно малых е > 0 (в силу непрерывности и конечности множества
вершин). Таким образом, v Н£ (у Е Ну).
Итак, (п — 1)-плоскость Н£ содержит лишь вершины грани G и
является опорной к extP. По следствию к теореме 1.3 G = Н£ А Р -
грань многогранника Р, что и требовалось. •
Следствие. Если для граней G и F многогранника Р выполнено
строгое включение G С F, то
1) грань G лежит на относительной границе грани F (G С rbF);
2) грань G имеет меньшую размерность, чем F (dimG < dimF — 1).
> Множество G, являясь гранью многогранника F, может быть от-
сечено опорной гиперплоскостью Н (в подпространстве affF, натяну-
том на F). И потому dimG < dimH = dim(af fF) — 1 = dimF — 1. Все
точки грани G, то есть точки грани F, лежащие в опорной плоскости
Н. являются, очевидно, граничными для F. •
10.	Минимальная грань, содержащая точку многогранника
Теорема 1.7. Пусть F и G - грани (возможно, несобственные)
многогранника Р. Если грань F содержит хотя бы одну относительно
внутреннюю точку xq грани G, то F содержит и всю грань G (коротко
F^riG ^9^ F DG).
> (Интуитивно-зрительная идея доказательства заключается в сле-
дующем. Если на несколько точек в 3-мерном пространстве натянуть
эластичную пленочку (образуя многогранник Р), то подвижная жесткая
плоскость (призванная отсечь грань F) не коснется плоских участков
пленки (например внутренних точек грани G многогранника), пока не
коснется всех точек, на которые эта грань натянута.)
Пусть грань F образована пересечением F = Рб\Нр многогранника
Р с опорной гиперплоскостью Нр, заданной уравнением (ж, пр) = а.
Причем Р С Н~, то есть (у, пр) < а для всех вершин многогранника
Р, и равенство достигается лишь на вершинах грани F.
Пусть xq - точка грани F, лежащая в относительной внутренности
грани G. Всякая точка xq Е riG (по теореме 1.2) может быть пред-
р
ставлена в виде х0 = Р/ХгЩ,	= Г А; > 0, г = 1,... ,р), где
г=1
{vp ... ,vp} - вершины грани G. Тогда (#о,й>) = А1(771,й>) + ... +
+Ар(Тр,nF) < (Ai + ...Хр)а = а. Причем равенство (#о,й>) = « (ко-
торое действительно имеет место в силу включения xq Е F С Нр)
достигается лишь при (у-рйр) = ... = (ур,пр) = а, то есть при вклю-
чении {771,... ,vp} С F. Отсюда видно, что и G = conv{vp... ,vp} С F.
•
Следствие 1. Если xq - относительно внутренняя точка грани
F многогранника Р, то F - наименьшая из граней многогранника Р,
содержащая точку xq (а, значит, F может быть получена их пересече-
нием).
Следствие 2. Если две грани F и G многогранника Р имеют хотя
бы одну общую внутреннюю точку, то они совпадают.
47
Следствие 3. Семейство множеств {riF}p\zp относительных
внутренностей всех граней выпуклого многогранника Р является разби-
ением множества Р (то есть покрытием без попарных пересечений).
11.	Многогранник как конечное пересечение полупространств
Из определения грани очевидно, что любая гипергрань F п-мерного
многогранника Р может быть представлена, как пересечение F = Н А
Р многогранника Р с опорной гиперплоскостью Н. причем Н вполне
определяется гранью F, поскольку dimH = dimF = n —1 (и фактически
H = affF).
Теорема 1.8. Пусть Р — п-мерный выпуклый многогранник в Еп,
F±,..., Fp - его гиперграни, Н±,..., Нр - опорные гиперплоскости, прове-
денные через эти грани, а Н(~,..., Нр - соответствующие им опорные
(замкнутые) полупространства к Р. Тогда
г=1
(1-4)
то есть п-мерный выпуклый многогранник Р является пересечением
всех опорных полупространств, соответствующих его гиперграням.
> Включение Р С Р|?=1 Н+ очевидно, поскольку по определению
опорного полупространства Р С н+ (г = 1,...,р) (см. рис. 1.6). Что-
бы доказать обратное включение, возьмем произвольно точку х Р
(см. рис. 1.6 а) и среди плоскостей Hi, соответствующих гипергра-
ням, найдем такую, которая строго отделяет многогранник Р и точ-
ку х (х е Н~, Р С 7?+), откуда будет следовать, что х Af=1 .
Для этого через всевозможные аффинно независимые наборы точек ви-
да {х, Vi,..., 77п-1} (где	- вершины Р) проведем (п — 1)-
плоскости 7Tj = aff{x,vi,...	Число их, очевидно, конечно. По-
скольку выпуклое n-мерное открытое множество intP не может быть
представлено объединением конечного числа (п — 1)-плоскостей тгj, в
нем найдется точка у0 Е intP, не лежащая ни в одной из плоскостей
7Tj. Очевидно, что [?/0,ж] А Р = [y^z], где z - граничная точка мно-
гогранника Р из интервала (^0,ж). И найдется собственная грань F,
содержащая точку z. (F = Н А Р, где Н - опорная гиперплоскость к
Р, проведенная в силу теоремы 4.2 через точку г.) Осталось показать,
что dimF = п — 1, а Н - искомая гиперплоскость. Действительно, если
dimF < п — 2, то среди вершин грани F найдется аффинно независимая
система ??i,..., vn-i такая, что z является их выпуклой комбинацией
(теорема Каратеодори 2.3 гл.1). Но тогда точка z принадлежит одной
из (п — 1)плоскостей ttj = aff{x, ..., что противоречит ее
выбору. Итак, dimF = п — 1. •
Упражнения
1.	Пусть ср - аффинное отображение Еп —> Ет, и Р - выпуклый
многогранник в Еп. Покажите, что его образ <^(Р) является многогран-
ником в Ет (см. упражнения §2 гл.1). Выведите отсюда, что проекция
выпуклого многогранника на А:-мерную плоскость есть снова выпуклый
многогранник.
2.	Плоскость Ак размерности к (0 < к < п — 1) называется опорной
к выпукому замкнутому множеству G, если множество G\Ak выпукло.
Покажите, что при к = п — 1 это определение совпадает с определением
опорной гиперплоскости, данным в п.1 §4 гл.1.
3.	Покажите, что для А:-мерного подмножества F (0 < к < п — 1)
многогранника Р следующие условия эквивалентны:
(a)	F — грань многогранника Р (т.е. найдется опорная к Р гипер-
плоскость Н, отсекающая грань F = Р А Н);
(Ь)	А:-мерная плоскость аффинной оболочки Ак = affF является опор-
ной к многограннику Р и отсекает множество F = Р А Ак,
(с)	найдется опорная к многограннику Р g-мерная плоскость Aq
(к < q < п — 1), отсекающая грань F = Р A Aq.
(Следствия (а) => (6) => (с) почти очевидны. Чтобы доказать
(с) => (а), рассмотрите ортогональную проекцию тг вдоль плоскости Aq
на (n — ^)-мерную плоскость An~q, которая переводит множество F в
точку х = 7r(F) = 7r(AQ), лежащую на границе многогранника 7г(Р).
Пользуясь тем, что Р \ F, а, следовательно, и тг(Р \ F) = 7г(Р) \ {ж}
выпуклы, примените теорему 1.3 и дополните Aq до опорной к Р (n —1)-
плоскости Н. отсекающей множество F.)
4.	Пусть М = {^i,,vm} - конечное множество точек про-
странства En, a Mi = {??i,... ,vk} и М2 = {^+1, • • •	(1 < к < т) два
его непустых дополнительных подмножества (Mi А М2 = 0, Mi U М2 =
= М), удовлетворяющие условию conv М± А а//М2 = 0.
Очевидно, что любая точка х выпуклой оболочки Р = conv М =
= conv{v±,... ,vm} может быть представлена выпуклой комбинацией
Ж — CVi??! Ч- . . . Ч- akVk -|- CV/^+1 “h • • • “h
где ai > 0 (i = 1,..., m), ai = 1-
(а)	Покажите, что если для х G Р хотя бы одно из (т — к) чисел
Qjfe+i,..., ат не равно нулю, то х i affMr (х е P\(affMi)), а в
противном случае х Е conv М^.
(Ь)	Выведите из п.(а), что conv М± = Р A (aff Mi) и Р\ (aff Mi) =
= Р \ (conv Mi).
(с)	Выведите из п.(а), что множество Р \ (affM±) выпукло.
5.	Пусть Mi — некоторое подмножество вершин многогранника Р,
а М2 — дополнительное к нему множество вершин (М2 = extP \ Mi).
Покажите эквивалентность следующих условий:
(а)	выпуклая оболочка F = conv М± есть грань многогранника Р;
(b)	aff М± A conv М2 = 0. (Воспользуйтесь результатами задач 3 и 4.)
§ 2.	Полиэдральные множества
1.	Полиэдральное множество. Определение
Полиэдральным множеством Q в пространстве Еп называют под-
множество Q С Еп, полученное пересечением конечного числа замкну-
тых полупространств, либо совпадающее с Еп.
Для всякого вектора п 0 и числа а Е R обозначим Н(п, а) -
гиперплоскость, заданную уравнением (ж, п) = а относительно пере-
менного радиус-вектора точки х Е Еп. А записи Н~(п, а), Н~(п, а)
50
[Н+(n. a). Н+(п. а)] будут обозначать открытое и замкнутое полупро-
странства, заданные неравенствами (ж, п) < а и (ж, п) < а [соответ-
ственно (ж, п) > а и (ж, п) > а]. Заметим, что Н+(п, а) = Н~(—п, — а).
В этих обозначениях любое полиэдральное множество Q Е Еп может
быть представлено записью
р
Q = Q
i=l
(2-1)
При этом для удобства далее везде будем считать, что все полупро-
странства Н~(п^ различны. Будем употреблять также сокращенные
обозначения Hi,	,....
Примеры 2-х и 3-мерного полиэдральных множеств Q2 и Q3 можно
увидеть на рисунках 2.1 а) и б).
Рис. 2.1
Заметим, что пересечение двух противоположных замкнутых по-
лупространств Н~,Н+ дает гиперплоскость К; любая А:-мерная плос-
кость Ак (0 < к < п — 1) может быть получена пересечением (п — к)
гиперплоскостей. А А:-мерное полупространство Пу может быть полу-
чено пересечением Пу = Ак A плоскости Ак с n-мерным полупро-
странством Ну (см. п.8 § 1. гл 1.). Поэтому любое А:-мерное поли-
эдральное множество Q (определенное как пересечение Q = П^=1 Пу
«/ «/
А:-мерных полупространств Пу, расположенных в пространстве Ак) мо-
жет быть также представлено в виде (2.1). И наоборот, любое А:-мерное
51
полиэдральное множество Q вида (2.1) может быть представлено в виде
Q = Ак А [Р| -еj Яр] = Р| -еj [Ак А Яр] = Р -ет Пр, где Ак - аффинная обо-
лочка множества Q, а {Яр}^/ - подсемейство из тех полупространств,
участвующих в пересечении (2.1), которые не содержат целиком плос-
кость Ак (см. п. 8 § 1 гл. 1).
Предложение 2.1. 1) Пересечение Q6\A полиэдрального множества
Q с любой плоскостью А есть снова полиэдральное множество.
2)	Пересечение Qi A Q-> любых двух полиэдральных множеств Qi и
Q2 есть снова полиэдральное множество.
2.	Ограниченные полиэдральные множества есть многогранники
Предложение 2.2. Граница п-мерного полиэдрального множества
Q, заданного представлением (2.1), равна
р
ЭД=и[Я4П^],	(2.2)
г=1
то есть состоит из точек множества Q, лежащих в плоскостях Ям огра-
ничивающих образующие полупространства Яр (г = 1,... ,р).
> intQ = intf\pi=1H7 = ^]pi=1intH7 = Clf=i ДГ-
To есть внутренность полиэдрального множества задается пересечени-
ем соответствующих открытых полупространств. Поэтому
9Q = Q \ intQ = Q n [Uf=1 н+] = Uf=i[<? п н+] = иг=1 [Q И Hi].
•
Теорема 2.3 (Минковского - Вейля). Для подмножества Q С Еп
следующие условия эквивалентны:
(a)	Q - выпуклый многогранник.
(b)	Q - ограниченное полиэдральное множество.
> Без ограничения общности будем считать, что Q — п-мерное
множество. (В противном случае можно перейти к подпространству
А = affQ.) Следствие (а)=>(Ь) доказано теоремой 1.8 § 1 этой главы.
Доказательство обратного следствия будем вести индукцией по размер-
ности п. Поскольку в соответствии с п.З § 1 этой главы многогран-
ник - это выпуклый компакт с конечным множеством крайних точек,
следует доказать лишь конечность множества extQ для произвольного
ограниченного полиэдрального множества Q. При п = 0 утверждение
очевидно. При п = 1 множество Q есть отрезок, и имеет две крайние
точки - его концы. Пусть теперь утверждение доказано для размернос-
тей к < п — 1, и Q — n-мерное ограниченное полиэдральное множество
вида
р ___
Q = П «г-
i=l
Любая из крайних точек х Е extQ является граничной (см. п.2 § 4
гл. 1) и принадлежит одному из множеств Qi = Hi A Q, число кото-
рых конечно. Однако каждое из Qi = Hi A Q является ограниченным
полиэдральным множеством размерности к < п — 1, и по предположе-
нию индукции имеет конечное множество крайних точек, которые (по
предл. 4.6 § 1 гл. 1) представляют все крайние точки множества Q, по-
павшие в сечение Qi = Hi A Q опорной плоскостью Hi. Таким образом
\extQ\ < сю. •
Замечание. Подчеркнем, что из теоремы Минковского - Вейля сле-
дует, что в отношении выпуклых многогранников как частного случая
полиэдральных множеств справедливы предложения 2.1 и 2.2 о пересе-
чениях и границе, а также все последующие утверждения относительно
полиэдральных множеств.
Упражнение 2.1. Докажите, что любая крайняя точка xq Е Q
полиэдрального множества (2.1) может быть представлена как пересе-
чение {То} = Q\iEl H(rii,ai) (I С {1,... ,р}) некоторого подмножест-
ва гиперплоскостей, ограничивающих полупространства представления
(2.1). Причем rank{rii}iEi = п. (Указание: покажите, что если множес-
тво уравнений (ж, nJ = соответствующих этим гиперплоскостям,
обратившихся в равенство в точке х = То, составляют линейную систе-
му уравнений ранга к < п, то точка То входит в множество Q вместе с
некоторой (п — ZJ-мерной окрестностью, а значит не является крайней.)
3.	Грани полиэдральных множеств
В этом параграфе мы расширим понятие грани, определив их для
произвольных полиэдральных множеств, а не только ограниченных (то
есть многогранников). Поэтому утверждения п.З будут служить обоб-
щениями соответствующих свойств выпуклых многогранников и могут
быть пропущены, если читатель хотел бы ограничиться изучением вы-
пуклых многогранников. Пункты же 4,5,6 содержат новые по сравнению
с § 1 свойства.
Как и в случае выпуклого многогранника гранью F полиэдрального
множества Q будем считать всякое его пересечение F = QC\H с произ-
вольной опорной к множеству Q гиперплоскостью Н. В силу предложе-
ния 2.1 любая грань F, как и всякое сечение полиэдрального множества,
является также полиэдральным множеством.
Предложение 2.4. Если F и G - грани полиэдрального множества
Q и G С F, то G является гранью и полиэдрального множества F.
>	Доказательство полностью повторяет доказательство теоремы 1.6.
• Обратное утверждение будет доказано позднее.
Следствие. Если грани G и F полиэдрального множества Q удов-
летворяют строгому включению G С F, то их размерности подчинены
строгому неравенству dimG < dimF. > •
Предложение 2.5. Пересечение F = Fi любого числа граней
Fi полиэдрального множества Q есть снова грань множества Q.
>	В случае пересечения конечного числа граней Fi доказательство
полностью повторяет доказательство теоремы 1.5 § 1 гл.1. В против-
ном случае всегда можно выбрать последовательность Fi, F2,..., Fk,...,
для которой выполняется строгое включение Gk+i := Fi С Gk :=
= П*=1 Fi (к = 1,2,...). Тогда размерности граней Gi подчинены нера-
венству dimGk+i < dimGk — 1 (к = 1,2,...). Из этого следует, что на
некотором m-ом шаге dimGm < dimF. С учетом включения F С Gm
это влечет равенство dimF = dimG и F = Gm. •
Лемма 2.6. Если произвольная опорная гиперплоскость Н к поли-
эдральному множеству Q содержит некоторую относительно внутрен-
нюю точку xq грани F полиэдрального множества Q. то Н содержит и
всю аффинную оболочку affF грани F, и тем более всю грань F. (Ко-
ротко F □ Р, Н A riF 0 => К D affF, Н D F.)
>	Пусть dimF = к. Доказательство почти полностью повторяет
доказательство теоремы 1.7 § 1 гл.1. Следует лишь вместо вершин грани
F взять любую аффинно независимую систему из (к + 1) точки в к-
мерной ^-окрестности Ок(хо,е) точки То, целиком лежащей в плоскости
affF так, чтобы точка xq была их строго выпуклой комбинацией.
Например подойдут точки у0 = То - 8^=1С,,	= То + Sei
(г =	где 8 > 0 - достаточно малое число, а ё1,... ,q - какой-
нибудь базис в А:-мерном линейном подпространстве Lk^F, подстилаю-
щем для плоскости affF. Тогда xq =	а включение xq Е Н
влечет {у0, ...,ук}СН и affF = aff{y0, ...,ук} CH. •
54
Предложение 2.7. Если F и G грани полиэдрального множества Q
и F A riG ф 0, то F3G. > •
Очевидно, что для полиэдрального множества Q = P|f=1 Hi все
пересечения вида Hi A Q является гранями той или иной размерности.
Предложение 2.8. Все гиперграни полиэдрального множества
Q = P|f=1 НЕ имеют вид ЩГ\ Q (г = 1,... ,р).
>	Предположим сначала, что размерность полиэдрального множес-
тва Q равна п. Пусть F - произвольная гипергрань множества Q и
Xq Е riF. Ясно, что х$ Е rbQ и (в силу замечаний п.1 и предложения
2.2) принадлежит одной из (опорных) гиперплоскостей Hi. Но тогда
(по лемме 2.7) affF С Hi и (в силу условия dimF = dimH = п — 1)
affF = Н. Поэтому F = Q A affF = Q A Hi. Случай dimQ = к < п
сводится к предыдущему при помощи замечаний пункта 1. •
4.	Неприводимое представление полиэдрального множества
Пусть Q - полиэдральное множество, заданное пересечением
г=1
(2-3)
Полупространство НЕ в представлении (2.3) называется избыточным,
если его исключение из пересечения (2.3) сохраняет множество Q, то
есть
р ___
о = ГМ-
i = 1
Очевидно, что полупространство Н- не является избыточным, если (и
только если) Q Q^=1 НЕ. то есть найдутся точки из Mj = P|^=i НЕ
не принадлежащие полупространству НЕ. Другими словами, при Q 0
имеются точки из Mj, лежащие по обе стороны плоскости Hj.
К примеру, двумерные полупространства Н\,Н§ на рисунке 2.2 а)
и трехмерное полупространство Н\ на рисунке 2.2 б) являются избы-
точными, в отличие от полупространств Н^, Н\. Н$.
Рис. 2.2
Представление (2.3) полиэдрального множества Q называется не-
приводимым, если ни одно из полупространств HJ не является избы-
точным, то есть удаление любого из них из пересечения (2.3) приводит
к множеству P|^=i	7^ Q.
Лемма 2.9. Для п-мерного полиэдрального множества
Q = P|f=1 следующие условия эквивалентны:
(а)	полупространство HJ в представлении (2.3) не является избы-
точным;
(Ь)	(intMj) A Hj = [QLi ] А Я? 0 (где НД = intH^) ;
(с)	dim[Hj A Q] = п — 1.
> Докажем импликацию (а) => (Ь). Прежде всего, поскольку
dimQ = n, intQ = riQ 0 (см. теорему 3.1 гл.1). Кроме того intQ С
С Я“, а множество intMj — P|^=i Яг~ открыто и включает в себя intQ.
Пусть у{} Е intQ (см. рис. 2.3 а) ), тогда у0 е HJ A intMj. По-
скольку полупространство HJ в представлении (2.2) не является из-
быточным, в множестве intMj найдется точка xq Е Н^ (лежащая по
другую сторону плоскости Hj). Тогда интервал (^о,То) пересекает ги-
перплоскость Hj в некоторой точке z Е (?/о,То) A Hj. Ив тоже время
весь полуинтервал [?/о,То) лежит во внутренности intMj множества Mj
(теорема 3.2). Таким образом, z Е Hj A (intMj) 0.
56
Рис. 2.3
(а)	=> (с). HjQQ = Я^П[П^. Ht ] С Я7П[П^. Ht ]	0 — открытое
множество в Hj. Поэтому dim[Hj A Q] = п — 1.
(Ь)	=> (а). Пусть х0 G Hj П [р^. Яг] (см. рис. 2.3 б) ). Тогда най-
дется открытый шар 0(То,г), целиком лежащий в открытом множестве
intMj = HP, то есть найдутся точки у1,у2 из intMj. лежащие в
шаре 0(То,г) по разные стороны от гиперплоскости Hj.
(с)	=> (Ь). Пусть dim[Hj A Q] = п — 1. Заметим, что тогда Hj A Q -
гипергрань, и пусть xq Е ri[Hj A Q]. Очевидно, что точка xq принадле-
жит всем замкнутым полупространствам HP (г = 1,...,п). Покажем,
что xq лежит и в открытых полупространствах HP (г = 1,..., п, г J).
Действительно в противном случае точка xq лежит в некоторой гипер-
плоскости Hi. Но тогда Hi содержит всю гипергрань Hj A Q, и ее аф-
финную оболочку Hj (лемма 2.3), то есть Hi = Hj, что противоречит
определению. •
Предложение 2.10. (1) Представление (2.3) п-мерного полиэд-
рального множества Q является неприводимым, если и только если
каждое из полупространств HP (j = 1,...,р) удовлетворяет условию
(с) (или (Ъ)).
(2) Неприводимое представление п-мерного полиэдрального множес-
тва Q может быть получено из любого представления (2.3) отбрасыва-
нием из пересечения всех полупространств HP, которые удовлетворяют
условию dim(Hi A Q) < п — 1.
(3) Неприводимое представление единственно (с точностью до пе-
ренумерации полупространств).
57
> Утверждения (1) и (2) очевидны. (3). Если Q = P|f=1 Hi =
= Pj=1 Jj^ - два неприводимых представления. Пусть xq - относитель-
но внутренняя точка гиперграни Qi = Hi A Q, тогда некоторая гипер-
плоскость Jj содержит точку х$ (предложение 2.2), тогда Jj D aff Qi =
= Hi (лемма 2.6). To есть Hi = Jj. •
Предложение 2.11. Для п-мерного полиэдрального множества Q,
заданного представлением Q = P|f=1 HF, следующие условия эквива-
лентны:	___
(а)	представление Q = P|f=1 HF неприводимо;
(Ь)	все множества Qi = QC\Hi (i = 1,... ,р) и только они являются
гипергранями полиэдрального множества Q.
> Докажем импликацию (а) => (Ь). Неприводимость представле-
ния Q = P|f=1 HF гарантирует, что dimQi = dim(Q A Hi) = п — 1
(г = 1,...,р) (предложение 2.10), а значит любое пересечение вида
Qi = Hi Г\ Q является (п — 1)-гранью (см. п. 3). Полнота списка гипер-
граней гарантирована предложением 2.8. Обратное - также следствие
предложения 2.10. •
5. Представление граней полиэдрального множества
Лемма 2.12. Если п-мерное полиэдральное множество Q задано
представлением
р ___
Q = А ЯГ(пЬ0!4),
г=1
то:
1)	Любая r-мерная грань (0 < г < п — 1) полиэдрального множества
Q может быть представлена в виде
2)	Относительная внутренность грани F имеет вид
i i <%i

(напомним Н- (nj^aj) - открытое полупространство).
3)	Система нормалей {щ}рсщ из равенства (2.4) к плоскостям
Hi, учавствующим в пересечении, имеет ранг к, удовлетворяющий ра-
венству к = п — г.
> 1) Доказательство 1-го пункта будет вестись по индукции размер-
ности п полиэдрального множества Q. Для п = 1 утверждение очевидно.
Предположим, что оно справедливо для размерности к < п — 1. Любая
r-мерная грань F (0 < г < п — 1) содержится в некоторой гиперграни
Qi множества Q. А потому является гранью полиэдрального множест-
ва Qi (предл. 2.4). (Действительно, достаточно взять точку xq Е riF и
найти в неприводимом представлении Q = P|f=1 HF плоскость Hj Э То,
и тогда гипергрань Qj = Hj A Q содержит всю грань F (предложения
2.2, 2.7).) Однако для полиэдрального множества Qi = Hj A [Qf=1 HF]
выполнено предположение индукции.
2)	Любая относительно внутренняя точка xq Е F принадлежит всем
открытым полупространствам Н^, ограничивающие плоскости Hi ко-
торых не содержат целиком грани F. (В противном случае xq Е Hi и по
лемме 2.6 F С Hi.) Обратное включение очевидно.
3)	Поскольку пересечение плоскостей [Q\FCH. Hi(rii,ai)] представ-
ляет собой плоскость решений линейной системы
(ж,Пг) = ai (i е {1,... ,р}, F С Hi),
а эта плоскость содержит r-мерную плоскость affF, то ранг однородной
системы удовлетворяет соотношению к = гапк{п)} /.с/ц <п — г.
Если бы ранг системы удовлетворял строгому неравенству
к = rank{ni}FCHi < п — г, то плоскость ее решений имела бы раз-
мерность р = п — к > г. Тогда произвольная точка xq Е riF (см.
упражнение 2.1) имела бы ^-мерную окрестность, содержащуюся в г-
мерной грани F, что невозможно. •
Предложение 2.13. Любая к-мерная грань F (0 < к < п — 1) п-
мерного полиэдрального множества Q может быть представлено как
пересечение не более чем (п — к) гиперграней Qi множества Q.
>	Достаточно в условии леммы 2.12 взять неприводимое представ-
ление, и тогда
A Hi p|Q= П [HiQQ]= A Qi, (2.5)
FCHi J	FCHi	FCQi
где Qi = Hi A Q - гиперграни множества Q.
Пусть {Qi, Q2, • • •, Qs} ~ семейство гиперграней полиэдрального
множества Q, содержащих грань F, то есть учавствующих в пересече-
нии (2.5). Ясно, что их количество s > п — г, поскольку ранг к системы
нормалей {й/}/'с//, к этим гиперграням в соответствии с леммой 2.12
равен к = п — г.
Выберем из конечной последовательности гиперграней
Qi,Q2,---,Qs подпоследовательность - • • ^Q't такую, что их пе-
ресечения
к
Gk = C\Qi (к = 1,... ,t)
i=l
удовлетворяют строгому включению Gk+i С Gk (к = 1,..., t—1). Тогда
dimGk+i < dimGk — 1. Отсюда ясно, что t < п — г. •
Заметим, что число t в некотрых случаях может быть сделано су-
щественно меньше, чем п — г. Например на рисунке 2.4 0-грань То
образована пересечением всего двух гиперграней Q\ и Q-> (t = 2), в то
время как п — г = 3 — 0 = 3.
Рис. 2.4
Предложение 2.14. Любая к-грань Fk (0 < к < п — 1) п-мерного по-
лиэдрального множества Q может быть получена пересечением
рк _ pk+i q рп-1 неК0т0р0й содержащей ее (к + Х)-грани Fk+1 и неко-
торой гиперграни Fn~r.
>	Действительно, если Fk = [П/.-а С//. Hi] A Q (где использовано не-
приводимое представление), то из множества {Hi}FkCH. можно выде-
лить конечную последовательность Н\.Н).....Нпк такую, что
рп-г _ А ... A Hr) A Q и dimFn~r = п — г (индекс сверху озна-
чает размерность грани). Следует лишь на каждом шаге добавлять ту
гиперплоскость Hi, которая не является избыточной для текущего пред-
60
ставления. Тогда для каждого I Е {к,... ,п — 1} справедливо равенство
_ pi+i Q П [ и в частности, Fk = Fk+1 А Нп_к. •
Следствие. Если G - грань полиэдрального множества F, a F -
грань полиэдрального множества Q. тогда G является гранью множес-
тва Q.
Упражнение 2.2.	1) Докажите, что любая А:-грань Fk
(О < к < п — 2) может быть получена пересечением некоторых двух
(к + 1)-граней.
2) И вообще любая А:-грань может быть получена пересечением не-
которых (к + г)-граней Fk = Fk+r (г > 1, к + г < п — 1), число
которых может быть сделано не большим, чем (г + 1).
6. Следствия для теории выпуклых многогранников
Предложения 2.13, 2.14, справедливые для произвольных полиэд-
ральных множеств, справедливы и для выпуклых многогранников, яв-
ляющихся ограниченными полиэдральными множествами. Это влечет
интересные следствия для семейства множеств вершин граней (различ-
ных размерностей) выпуклого многогранника. Для краткости F будет
обозначать множество вершин грани F.
Предложение 2.15. Пусть Р - выпуклый п-мерный многогранник.
1) Множество вершин Fk любой k-грани Fk может быть получено
пересечением Fk = Дп-1 множеств вершин некоторого набора гипер-
граней.
2) Fk можно также предствитъ как пересечение Fk = Fk+1 ^Fn~r
вершин некоторой (к + Х)-грани и гиперграни Fn~r. > •
Отсюда в частности следует, что, имея в распоряжении семейство
F™-1,..., РД”* множеств вершин всех гиперграней многогранника Р,
можно получить семейство множеств вершин всех А:-граней
(А: = 0,1,..., п — 1). Для этого следует провести (п — 1) шаг, каждый из
которых понижает размерность известных граней на единицу.
Действительно, пусть известно семейство Р^+1,..., РДД*
(к + 1)-граней многогранника Р. Составив всевозможные пересечения
ту1 П Т"-1 (г = 1,... ,Pk+i, j = 1,    получим семейство {GJ
подмножеств вершин, соответствующее семейству граней, содержаще-
му в себе все А:-грани многогранника Р. Однако все r-грани Gi размер-
ности г < к можно легко отбросить, используя тот факт, что для каждой
из них найдется соответствующая А:-грань Gk, содержащая ее в качест-
61
ве собственного подмножества (G^ С G^). То есть следует исключить
все подмножества G*, которые являются собственным подмножеством
некоторого другого Gj из множества {G/}.
Упражнения
1.	Покажите, что образ n-мерного полиэдрального множества
Q С Еп при аффинном отображении р : Еп —> Ет есть снова поли-
эдральное множество С Em (см. упр. 1 (г) к §2 гл. 1).
2.	Покажите, что множество вершин и множество крайних то-
чек произвольного полиэдрального множества совпадают. (Используйте
упр. 2.1.)
3.	Покажите, что утверждения задачи 3 к §1 гл. 2 справедливы и
в случае, когда Р — полиэдральное множество.
4.	Покажите, что определение грани F полиэдрального множества
(и, в частности, выпуклого многогранника) может быть дано следую-
щим предложением, обобщающим понятие крайней точки:
(d) F - выпуклое подмножество (выпуклого замкнутого) множества
Р, удовлетворяющее следующему условию. Если любой интервал (ж,^)
с концами в точках ж, у множества Р содержит точки из множества F
((ж, у) A F 0), то ж, у G F (а, значит, и отрезок [ж, у] С Р).
(Используйте определение грани из п.(Ь),(с) задачи 3 к §1 гл.2.
Следствие (6) => (d) почти очевидно. Для доказательства обратного наи-
большую трудность представляет доказательство включения
(affF) А Р С F (то есть F включает в себя всю часть своей аффинной
оболочки, лежащей в множестве Р). Случай dimF = 0 очевиден. Для
dimF > 1 следует взять некоторую точку уо Е ri F 0, лежащую в
F вместе с А:-мерной окрестностью (см. теорему 3.1 гл.1). Тогда для
любой точки х Е affF отрезок [ж,^о] можно продлить в Р за точку
Уо до точки z Е F. И тогда из условий г Е (ж,г) А Р, ж, г Е Р в
соответствии с (d) следует ж, z Е F.}
Глава 3. РАЗБИЕНИЯ ПРОСТРАНСТВА Еп, ЗАДАВАЕМЫЕ
РАВНОМЕРНО-ДИСКРЕТНЫМИ СИСТЕМАМИ ТОЧЕК
§1. Разбиения на многогранники
Семейство {МД множеств С Еп называется локально-конечным
расположением, если любая точка пространства обладает окрестностью,
которая пересекается только с конечным числом множеств семейства.
Не оговаривая, мы предполагаем рассматриваемые семейства множеств
локально-конечными расположениями. Семейство {МД образует упа-
ковку в множестве Л4 С Еп, если Mi С А4 при всех i и внутренности
множеств семейства попарно не пересекаются. Семейство {МД, обра-
зующее упаковку в множестве Л4 С Еп и покрытие этого множества,
называется разбиеним множества.
Объектом нашего изучения в этой главе будут некоторые специаль-
ные разбиения пространства Еп на многогранники. Под словом ’’мно-
гогранник”, если не оговаривается какие-либо другие его свойства, мы
понимаем выпуклый конечногранный п-мерный многогранник в про-
странстве Еп. Такой многогранник мы будем рассматривать или как
пересечение конечного числа полупространств, или как выпуклую обо-
лочку конечного числа точек. Многогранник и его грани всех размер-
ностей, если не оговорено противное, считаются замкнутыми множест-
вами. Мы будем пользоваться как известными следующими свойства-
ми, в некотором смысле тривиальными, рассматриваемых многогран-
ников:
1.	Любая грань некоторой размерности многогранника Р является
пересечением многогранника с некоторой гиперплоскостью Н, отделя-
ющей Р от полупространства, свободного от точек Р. Всякое такое
пересечение даёт грань некоторой размерности многогранника Р (см.
п.5 § 1 гл. 2).
2.	Всякое пересечение граней многогранника Р является его гра-
нью и любая грань может быть получена пересечением его гиперграней
(п. 8 § 1, предл. 2.13 гл. 2).
3.	Если грань F многогранника Р содержит относительно внутрен-
нюю для некоторой грани G точку х, то грань G целиком содержится
в грани F (п.10 § 1 гл. 2).
4.	Если две грани многогранника содержат относительно внутрен-
63
нюю для каждой из них общую точку, то они совпадают.
5.	Непустое пересечение конечного числа многогранников является
также многогранником (предл. 2.1, теор 2.3 § 2 гл. 2).
Разбиение на многогранники называется нормальным, если всякое
непустое пересечение двух многогранников разбиения есть общая целая
грань этих многогранников; в противном случае разбиение называется
ненормальным.
Для любой точки х многогранника Р найдется минимальная грань
F многогранника Р, содержащая эту точку (х Е riF, см. п. 10 § 1 гл. 2).
Точку, принадлежащую минимальным граням различной размерности
двух или большего числа многогранников некоторого разбиения будем
называть точкой ненормальности разбиения. Очевидно
Предложение 1.1. Разбиение является тогда и только тогда не-
нормальным, когда среди точек множества Л4 С Еп, несущего разбие-
ние, есть точки ненормальности.
Примеры нормального и ненормального разбиения плоскости на па-
раллелограммы можно увидеть на рисунках 1.1 а) и б).
Пусть семейство выпуклых многогранников образует нор-
мальное локально-конечное разбиение Ф множества Л4 С Еп. В этом
случае можно говорить не только о гранях того или иного многогранни-
ка разбиения, но и о гранях разбиения. Рассматривая множество всех
граней некоторого нормального разбиения, будем относить к их числу
и сами многогранники разбиения, называя их гранями размерности п.
Две грани G± и G2 разбиения могут находиться по отношению друг
к другу в одном из двух отношений принадлежности'.
1) Gi С G2 или G2 cGi;
2) ни одно из включений 1) не имеет места.
В случае первого отношения будем говорить, что грани инцидент-
ны, в случае второго — неинцидентны.
Разбиение Ф рассмотрим как множество {Fi} всех его граней:
Ф = {Ft}.
Два нормальных разбиения Ф = {Fi} и Ф = {Gm} одного и того же
множества Л4 С Еп называются комбинаторно двойственными, если
между гранями этих разбиений можно установить такое взаимно одно-
значное соответствие Fs > Gs. при котором 1) сумма размерностей
любой пары соответствующих граней Fs и Gs равна п; 2) любая пара
граней Fs.Fq одного разбиения и соответствующая ей пара Gs,Gq гра-
ней второго разбиения одновременно неинцидентны либо инцидентны и
отношения включения противоположны.
Примером комбинаторно двойственных разбиений являются разби-
ения плоскости на правильные треугольники и правильные шестиуголь-
ники — см. рис. 1.2, где комбинаторная двойственность задаётся соот-
ветствием двумерных граней одного разбиения их центрам симметрии
как 0-мерным граням второго разбиения.
Для дальнейшего нам потребутся приведённая ниже лемма общего
характера из геометрии евклидова пространства.
Лемма 1.2. Пусть конечное множество точек М = {гп±, ...,mq}
определяет к—мерную плоскость Р^. (1 < к < п), и все точки этого
множества лежат на (к — 1)-мерной сферической поверхности с
центром в точке q. Тогда множество точек, равноудалённых от то-
чек множества М, представляет собой (п —к)-мерную плоскость Рп-к,
ортогональную плоскости Р^ и пересекающуюся с ней в точке q.
> Пусть точки mi,	образуют полное подмножество М* ли-
нейно независимых точек множества М. Точка х тогда и только тогда
равноудалена от всех точек множества М*, когда она удовлетворяет к
равенствам
|ж — mi| = ... = |ж — w+i|.
Переписав эти равенства в виде
|ж — т^| =	— m^+i|, / =
после небольших преобразований получаем систему уравнений
mi + mfe+i
)(w - mfc+i) = О,
i = 1,..., к.
Каждое из уравнений полученной системы — это уравнение гиперплос-
кости пространства Еп. проходящей через точку |(т* + W-+1)-
i Е {1, 2,..., к} перпендикулярно вектору rfii — rrik+i, а их пересечение
задаёт плоскость Рп-к, 0 которой говорится в лемме. Точки множества
М \ М* удалены от каждой из точек плоскости Рп-ь на то же расстоя-
ние, что и точки множества М*, поскольку
(тр — ж)2 = ([тр — q] + [q — ж]) = [тр — q]2 + [q — х]2 = г2 + [q — х]2
(р = 1,..., к + 1,..., д), где г - радиус А:-мерной сферы •
(Иллюстрацию к доказательству леммы см. на рис. 1.3 а),б).)
Заметим, что при к = п плоскость Pn-k, о которой говорится в
лемме 1, нульмерна, то есть представляет собой точку — центр сфери-
ческой поверхности cjn-i, определяемой множеством М.
66
§2. Равномерно-дискретные системы точек
Множество точек L = {Ц} п-мерного евклидова пространства Еп
называется равномерно-дискретной системой, или (г, R)-систе-
мой, если
1) для
г0 = inflfi - lj\, i^j,
выполнено го > 0 (го — радиус дискретности), и
2) для
Ro = sup|x — Ц\, х Е Еп, Ц G L
выполнено Rq < сю (Ro — радиус равномерности).
(При желании указать на конкретные значения радиусов дискрет-
ности и равномерности будем называть точечную систему (го,Яо)-сис-
темой либо подставлять числовые величины вместо го и Rq.)
Условия 1),2) эквивалентны следующим: 1) в открытом шаре ради-
уса не больше го с центром в любой точке системы L нет других точек
системы; 2) в любом замкнутом шаре радиуса не меньше Rq найдётся
хотя бы одна точка системы L.
(го, Яо)"система имеет счётную мощность: конечное множество то-
чек не может удовлетворять условию 2), а более чем счётной мощности
— условию 1.
Через Q(a, р) далее будем обозначать n-мерный замкнутый шар с
центром в точке а и радиусом р. Согласно определению множество
шаров
д)
образует упаковку в пространстве Еп, а множество шаров
Ц С L
Q(Z^, Яо),
(2)
— покрытие пространства Еп.
Примером равномерно-дискретной системы является точечная
решётка — множество целых точек относительно произвольного декар-
това базиса в пространстве Еп (см. рис. 2.1).
67
ej____
0 ё,
Рис. 2.1
Упражнения
1.	Приведите примеры бесконечных дискретных множеств, не яв-
ляющихся (го,Яо)"системами (Л) = О или = оо).
2.	Назовём отношение r(L) = показателем равномерности
-системы L. Докажите, что при п > 2 имеет место неравенство
t(L) < 1, а в случае r(L) > | система является плотной — её нельзя
дополнить ни одной новой точкой с сохранением радиуса дискретности
го-
Докажите, что при п > 3 справедлива оценка r(L) <
При каких значениях п множество целых относительно ортонор-
мированного базиса точек пространства Еп образует плотную (го,7?о)-
систему?
3.	Следуя Б.Н.Делоне, п-мерный шар пространства Еп, не содержа-
щий внутри точек (го, Яо)"системы Ь, назовём пустым шаром системы
L. Докажите, что у всякой (го, Яо)"системы L С Еп найдётся пустой
шар радиуса, не меньшего, чем
4.	Назовём пустой шар n-мерной равномерно-дискретной системы
стационарным пустым шаром, если он содержит на своей поверхнос-
ти п + 1 линейно независимую точку системы. Докажите, что полное
множество замкнутых стационарных шаров системы образует покры-
тие пространства Еп.
68
§ 3. Области Дирихле-Вороного точек (г, Я)-систем
и разбиение Дирихле-Вороного
Пусть L = {Ц} - равномерно-дискретная (го, Яо)"система в про-
странстве Еп.
Определение. Областью Дирихле-Вороного	точки Ц системы
L (коротко - областью Д-В) называют множество таких точек х Е Еп,
расстояние каждой из которых до точки Ц не превосходит ее расстояния
до любой другой точки множества L.
Таким образом, У(Ц) = s х Е Еп
\х — Ц\ < \х — lq\,
vr9 еад}}.
Упражнение 3.1. Покажите, что область Д-В точки Ц Е L есть
множество всевозможных центров ’’пустых” шаров (не содержащих
внутри точек (г, Я)-системы L), которые ’’опираются” на точку I (то
есть содержат точку Ц на своей поверхности).
Предложение 3.1. Для каждой точки х пространства Еп най-
дется непустое конечное множество £% = {Цг,... Цк} ближайших к ней
точек системы L.
> В силу равномерности системы L в замкнутом шаре Я(ж,7?о) с
центром х и радиусом Rq содержится непустое подмножество {1Р} то-
чек системы L (см. рис. 3.1). Это множество конечно, поскольку замк-
нутые шары Q(Zp,To/2), не пересекаясь, лежат в шаре 0(ж,Яо +го/2).
Остается из конечного множества {1Р} выбрать подмножество на
котором достигается минимум расстояния \х — 1Р\. •
69
Следствия. 1) Любая точка х пространства Еп принадлежит не-
нулевому конечному количеству областей ... ,V(lik) Дирихле-Во-
роного.
2) Совокупность всех областей Д-В образует покрытие простран-
ства Еп.
Для любой фиксированной области Дирихле-Вороного отметим
два включения.
Предложение 3.2.	ro/2) С У(^) Q
где Q(Z^,ro/2) и Q(Zi,Bo) _ замкнутые шары с центром в точке Ц и
радиусами го/2 и Rq.
> Действительно, если точка х пространства Еп принадлежит замк-
нутому шару Q(Zi,ro/2), и предположить, что х V(/J, то найдется дру-
гая содержащая ее Д-В область V(lq) (для некоторой точки lq Е Ь\{Ц}).
А значит |ж — lq\ < |ж — Ц\ < vq/2 и \Ц — lq\ < \Ц — ж| + |ж — lq\ <
< го/2 + го/2 = го, что противоречит определению радиуса дискретнос-
ти го для (го,Яо)"системы L.
Для доказательства второго включения предположим, что точка х
пространства Еп не принадлежит замкнутому шару Я(^,Яо)5 то есть
\х — Ц\ > Rq. Тогда по определению радиуса равномерности Rq в шаре
радиуса Rq с центром в точке х найдется точка lq системы L, отличная
от Ц, и такая, что \х — lq\ < Rq < \х — Ц\. А это означает, что Ц не
является ближайшей точкой системы L для ж, и потому х V(/J. •
Рисунки 3.2 а,б иллюстрируют включения предложения 3.2 для
разбиения на прямоугольные и 6-угольные области Дирихле-Вороного,
70
определенного равномерно-дискретной системой ь = построенной
как плоская решетка на основе прямоугольника и правильного треуголь-
ника (см. также рис. 1.2 и 2.1).
Рассмотрим теперь геометрическое строение области Дирихле-
Вороного. Из определения очевидно, что х Е У(Ц) тогда и только тогда,
когда выполняются неравенства
\х — Ц\ < \х — lq\,
После возведения в квадрат и проведения несложных преобразований
неравенства получают эквивалентную форму:
(3.1)
При фиксированной точке lq последнее неравенство является заданием
полупространства 7rQ(Z^)? содержащего внутри точку Ц и ограниченного
гиперплоскостью П6/ / с уравнением
1 / —	— \
которая проходит через центр + отрезка
перпендикулярно
вектору Ц — lq (рис. 3.3 а). Очевидно, что П6/ / = П/ 6/ = тг^(Z^) Н тг* (ZQ).
71
Так как неравенства (3.1) должны быть выполнены для всякой точ-
ки lq Е	то область Дирихле-Вороного V(li) точки Ц (го,7?о)-
системы L представляет собой пересечение
(^г) ?
lq Е L\{li |,
(3.2)
где 7rq(li) - полупространства, состоящие из точек, которые удалены от
точки Ц не больше, чем от точки lq (см. рис. 3.3 б).
Отсюда в частности видно, что области Дирихле-Вороного V(/J то-
чек Ц системы L представляют собой замкнутые выпуклые множества
(как пересечение замкнутых выпуклых полупространств).
В представлении области Д-В в форме (3.2) множество полупрост-
ранств, участвующих в пересечении, можно ограничить.
Предложение 3.3. Для любого фиксированного числа е > 0 область
Дирихле-Вороного У(Ц) представляет собой пересечение
тгр (li) у	£ L A Q (Z^, 2(До + £)) \ {h} )	(3-3)
p
конечного числа полупространств тгр(Ц), соответствующих всем точ-
кам 1Р системы L , лежащим в шаре Q(^,2(/?o + £)) (за исключением
точки li).
> Очевидно, что пересечение (4) является подмножеством пересе-
чения (5). Чтобы доказать противоположное включение предположим,
72
что х V(li) =	(lq C	и докажем, что тогда точка
х не принадлежит и пересечению (3.3). Действительно, тогда на от-
резке Rx
найдется точка д. лежащая на границе дУ(Ц) области Д-В
V(/J. Из свойств замкнутого выпуклого множества У(Ц) следует, что
[h.y] Q WJ, (у,%] Q (Еп\У(ЦУ), и у е Q(Z*,#o) (см. предл. 3.2). Тогда
на интервале (?/, х) найдется точка г, принадлежащая открытому шару
0(li,Ro + в) (см. рис. 3.4).
Предположим, что все полупространства 7гр(1{), для всех точек 1Р
системы L, лежащих в замкнутом шаре Q(/^, 2(Яо + £)) содержат точку
z. Все же полупространства тг5 (/*), определенные точками ls Е L, лежа-
щими вне шара Q(^,2(/?o + s)), содержат z вместе с открытым шаром
Яо+ё) • Отсюда следует, что z Е V(ZJ, что неверно. Итак, найдется
полупространство тгРо (/^), lPo Е L AQ (/*, 2(Яо +£)) ? не содержащее точки
г, а значит и точки х (поскольку Ц Е лРо(Ц) ). Поэтому х П^р^г),
(lp Е L A Q(/i, 2(Ro + £))} • •
Следствие. Область Д-В точки Ц (г -системы L представляет
собой пересечение
¥(1г) = А (/г) ,
q
(3-4)
конечного числа полупространств 7rq(li), соответствующих всем тем
точкам lq системы L, исключая точку R которые принадлежат шару
2Rq) .
> Действительно, шаровой слой
0(Гй2(Ло+е)) \ 0(Гй2Ло), (г > 0),
в силу существования радиуса дискретности системы L содержит лишь
конечное множество точек этой системы и, следовательно, начиная с
некоторого достаточно малого значения е, не содержит их вовсе. •
Из предложений 3.2 и 3.3, а также из теоремы Минковского-Вейля
(теор. 2.3 § 2 гл. 2) вытекает
Теорема 3.4. Область Дирихле-Вороного V(li) любой точки Ц
равномерно-дискретной системы L в пространстве Еп представляет
собой п-мерный выпуклый ограниченный конечногранный многогранник.
Предложение 3.5. Любое непустое пересечение У(Ц) A У\1к) двух
областей Д-В точек (tq^Rq)-системы представляет собой грань каждо-
го из многогранников У(1г), У(1к)-
>	Возращаясь снова к определению областей Дирихле-Вороного, лег-
ко видеть, что пересечение двух областей имеет вид:
W = У(Ц) А У(Гк) =
(3-5)
Действительно, в случае, когда пересечение W = V(li) С\У(1к) не пус-
то, плоскость является опорной для многогранника V(li) (так как
Q я>(^))5 и, следовательно, W является гранью многогранника
V(Q. •
Теорема 3.6. Совокупность областей Дирихле-Вороного (tq,Rq)-
системы образуют нормальное разбиение пространства Еп.
>	Немедленно следует из предложений 3.2 и 3.5. •
Разбиение пространства на области Д-В точек системы L называ-
ется разбиением Дирихле-Вороного (разбиением Д-В) этой системы.
Возращаясь к пересечению (3.5), видим, что возможны три различ-
ных случая:
1)	W = У(Г,) АП^ = 0;
2)	W = V(li) А 1Ц,к	0,	0 < dimVP < п - 1;
3)	W = V(fJ А	0,	dimW = п - 1.
Опираясь на результаты гл.2 о неприводимом представлении вы-
пуклых конечногранных многогранников как полиэдральных множеств
(п. 4 § 2 гл.2), видим, что из пересечения (3.4), дающего представле-
ние области Д-В V(Zz)? можно исключить все те полупространства 7rp(ZJ,
ограничивающие гиперплоскости которых удовлетворяют условию
1) или 2). Кроме того, из предложения 2.11 гл.2 следует, что случай
3) описывает все гиперграни многогранника Заметим также, что
точки 1к системы L, удовлетворяющие условиям 2) или 3), лежат в шаре
Q(Zi, 2Яо) •
Итак, имеем:
к
74
где в пересечении участвуют полупространства 7ц.	, соответствую-
щие всем точкам Ik системы L, лежащим в шаре Q 2Яо) и удовлетво-
ряющим условию dim^V(Z^) И = п — 1.
Установленное формулой (3.5) представление любой грани много-
гранника V(li) и, в частности, гиперграни как некоторого пересече-
ния V (Z^i) А V (Z^ ), а также тот факт, что любая грань многогранни-
ка У(Гг1) является некоторым конечным пересечением его гиперграней
(см. предл. 2.13 гл.2), позволяет говорить, что любая грань W мно-
гогранника V(Zii) имеет представление W = П^=1
= V(Fii) А ... A Тем самым получено
Предложение 3.7. Любая грань W разбиения Д-В может быть
представлена в виде пересечения областей Д-В
q
(3.6)
(То есть представляет собой множество точек х пространства Еп,
для которых одновременно к точек 1^,..., Цк системы L являются бли-
жайшими.)
И обратно, любое непустое пересечение (3.6) областей Д-В явля-
ется гранью каждого из многогранников У(Ггх),...,	• > •
Однако, такое представление граней разбиения Д-В неоднозначно.
Например, на рис. 3.5 вершина s разбиения Д-В, построенного на точках
L = {Ц, Ik Am, • • •} имеет представления s = V(li] A V(lk) —
nv(/;) nv(ft) пр(й).
Рис. 3.5
Для установления однозначности максимизируем количество точек
liq, входящих в представление (3.6).
75
Определение. Конечная система точек Cw — {^1, • • • Q L
(го, Яо)"системы L называется максимальной образующей для грани W
разбиения Д-В, а грань W - порожденной системой точек Cw, если
(1)	= ПГ=1 V(Fife);
(2) Для любой конечной системы Cw С L, удовлетворяющей усло-
вию (1), выполнено включение Cw С Cw-
Предложение 3.8 Для любой грани W существует единственная
максимальная образующая система Cw • Она состоит из всех точек lj
системы L, Д-В области V(lj) которых содержат грань W, то есть
включение W С эквивалентно lj Е Cw-
> Существование множества точек из системы L, удовлетворяю-
щего условию (1), следует из предложения 3.7. Конечность множества
точек lj Е L, таких, что W С V(Zy), гарантируется тем, что любая точ-
ка грани W входит лишь в конечное число областей Д-В (см. следствие
предложения 3.1). •
Упражнение 3.2. Покажите что грань W разбиения Д-В, порож-
денная максимальной образующей системой {Цг,..., Цт } есть множес-
тво всевозможных центров ’’пустых” шаров (не содержащих внутри то-
чек (г, Я)-системы L), которые ’’опираются” одновременно на все точки
lir,..., Цт (то есть содержат точки ,..., Цт на своей поверхности).
Сравните с упражнением 3.1 этого параграфа.
Следующие три предложения раскрывают некоторые важные свой-
ства максимальной образующей системы для грани разбиения Д-В. Зна-
ние этих свойств необходимо и в следующем параграфе при рассмотре-
нии L-разбиения (го, Яо)"системы.
Лемма 3.9. Пусть множество Сх =	С L есть множест-
во ближайших точек системы L для произвольной точки х Е En\L. И
пусть dimZ^ = k, a Pn~k — (п — к)-мерная плоскость точек, равноу-
даленных от точек множества Сх (см. лемму 1.2 § 1).
Тогда существует такая е-окрестностъ UJ точки х, что для лю-
бой точки у из пересечения UJ А Рп-к ближайшими точками систе-
мы L являются точки множества Сх и только они (то есть Су = Сх).
(Другими словами, точку х всегда можно ’’слегка сдвинуть” в эк-
видистанционной плоскости Рп-к, чтобы ближайшими к ней остались в
точности те же точки системы L.)
76
множества = {Цд}™=1-
в шар О(ж,р) и не содер-
в силу существования ра-
= р, если М = 0, либо
при М 0 получим неравенства R < р* < р.
> Пусть R = \х — Ц \ (q = l,...,m) - расстояние от точки х до
ближайших точек системы L (см. рис. 3.6). И пусть О(ж,р) - откры-
тый шар радиуса р > Я, содержащий точки
Множество М точек системы L, попавших
жащихся в системе £% =	конечно,
диуса дискретности. Поэтому, положив р*
р* = min< |ж — /|,
(Заметим, что открытый шар О(ж,р*) не содержит других точек систе-
мы L, кроме множества £% = {/гд}^=1-)
Положим теперь s = (р* — Я)/2 (s > 0), то есть р* = R + 2s.
Тем самым имеем: 1) замкнутый шар Q(x,2?), не содержащий точек
L, кроме точек системы £% =	лежащих на его поверхности;
2) открытый шар О(х, 2?+2s), не содержащий точек L, кроме множества
£% =	Добавим к ним еще s-окрестность
шар O(x,s).
Возьмем теперь произвольную точку у из
строим вокруг нее замкнутый шар Q(^, 7? + s).
точки х - открытый
\х,£)\\^п-к И не-
очевидные включе-
ния Q(x, R) С^В + г) СО(ж, R + 2s) показывают, что Q (т/, R + s)
не содержит точек системы L, кроме принадлежащего ему множества
у множеством
£х =	А значит £% =
ближайших точек системы L. •
остается для
Предложение 3.10. Пусть £% —	L множество ближай-
ших точек системы L для произвольной точки х Е En\L, тогда
77
1)	множество W = V(Ziq) - грань Д-В разбиения;
2)	х - относительно внутренняя точка грани W (х Е riW);
3)	dim И7 + dimZ^ = п;
4)	Сх ~ максимальная образующая система грани W
(Ew — Ex ) •
> Множество W является гранью разбиения Д-В в силу предложе-
ния 3.7.
Пусть k = dimZ^. Согласно представлению (3.5), грань W лежит
в (п — &)-мерной плоскости Pn~k точек, равноудаленных от точек мно-
жества £х (см. лемму 1.2 §1). Поэтому dimly < (п — к). Однако точка
х лежит в грани W вместе с (п — &)-мерной окрестностью (предложение
3.8). И поэтому dimly = п — к , и х Е riW.
Докажем максимальность системы Z^. Пусть W = П^=1 V(Zjfe) =
= < х Е Еп \х — lj11 = ... = \х — ljp | < \х — Z~|, I Е Z/| - другое представ-
ление грани W. В силу того, что каждая из точек lj1,..., 13-р по своему
определению является одной из ближайших точек системы L для точек
грани W, в том числе и для х Е riVK, то имеем: {lj1,..., lj } С Z^ =
Предложение 3.11. Для любой грани W разбиения Д-В справедли-
во:
1)	Ex = Ew, то есть множество ближайших точек системы L
для любой относительно внутренней в W точки х Е nW совпадает с
максимальной образующей системой грани W:
2)	dimll7 + dim£vv = п.
3)	грань W и множество Ew лежат в ортогональных плоскостях
aff W и aff Ew, пересекающихся в единственной точке q — центре
k-мерной сферы (к = dim Ew), лежащей в плоскости aff Ew и содер-
жащей все точки множества Ew •
> Пусть W' - грань разбиения Д-В, образованная системой Е%-
Включение Ew Q Ex доказывается аналогично пункту 4 предложения
3.10. Поэтому W' С W. С другой стороны, W' содержит относительно
внутренннюю для грани W точку х и потому W' D W (см. теорему
1.7 и предложение 2.7 гл. 2). •
Следствие. Максимальная образующая система Еу для любой вер-
шины v разбиения Дирихле-Вороного имеет размерность п.
Из выведенных выше свойств максимальных образующих систем
непосредственно следует
Теорема 3.12. Множество т = {^15... Jim} С L является макси-
мальной образующей системой для некоторой Д-В грани тогда и только
тогда, когда найдется точка х Е En\L, для которой т является мно-
жеством ближайших точек системы L (то есть т = Сх), или, другими
словами, найдется замкнутый шар Q(x,p), не содержащий точек сис-
темы L, кроме точек множества т, лежащих на его поверхности.
Упражнения
1.	Докажите, что множество V = {^} вершин разбиения Д-В
равномерно-дискретной (го, Яо)"системы также является равномерно-
-дискретной системой. Что можно сказать о радиусе равномерности и
радиусе дискретности этой системы по сравнению с аналогичными ра-
диусами го,Яо исходной системы?
2.	Что представляет собой разбиение Д-В n-мерной кубичной
решётки?
3.	Найдите области Д-В системы точек на плоскости, представ-
ляющей собой объединение множества целочисленных точек относи-
тельно некоторого ортонормированного репера и множества точек вида
(х + |, у + |), где х. у — целые числа.
§ 4. L-многогранники (многогранники Делоне) (г, Я)-систем
и L-разбиения, задаваемые этими системами
1.	Метод Б.Н. Делоне ’’пустого шара”. L-многогранник
Здесь, как и в предыдущем параграфе, L = {Ц} означает некоторую
произвольную фиксированную (го, Яо)"системУ пространства Еп.
В изложении вопросов L-разбиения будем идейно следовать извест-
ной работе Б.Н.Делоне ’’Геометрия положительных квадратичных
форм” (журнал ’’Успехи математических наук”, Вып.Ш, 1937г.), да-
ющей яркую геометрическую иллюстрацию этого понятия. Картину
дополнят параллельно введенные замечания о связи с разбиением Ди-
рихле-Вороного, отмеченные в тексте отступом и двойной чертой слева
и необязательные при первом чтении.
Начнем с цитаты из вышеназванной работы. ’’Рассмотрим шар,
79
- увеличивающийся, уменьшающийся и как угодно передвигающийся
между точками системы L [авторские обозначения изменены], - подчи-
ненный лишь одному условию: не содержать внутри себя точек этой
системы. Мы будем называть такой шар ” пустым”. Начнем увеличи-
вать радиус пустого шара, оставляя его центр на месте, пока шар не
наткнется своей поверхностью на какую-нибудь точку системы L. ...
Это наверное произойдет, так как ... [в системе L] ... не может быть
пустого шара, радиус которого был бы больше, чем Rq.
Будем теперь дальше увеличивать радиус пустого шара, отодви-
гая его центр от этой точки или, если точек, на которые он наткнулся,
было сразу несколько, - от того линейного подпространства, которое
определяется этими точками. Продолжая так дальше, мы убедимся,
что в системе L существует пустой шар, на поверхности которого ле-
жит п-мерный комплекс точек этой системы, ... [содержащий] не менее
nT 1 точки... [Такой шар называют стационарным. поскольку он жест-
ко зафиксирован этими точками - его центр и радиус однозначно ими
определяются.]
Построив выпуклую оболочку комплекса всех точек системы L, ле-
жащих на шаре ..., мы получим выпуклый многогранник, вписанный в
этот шар, с вершинами в точках комплекса. Обозначим этот многогран-
ник через L.”
Рис. 4.1	7
(Все этапы движения пустого шара на плоскости (то есть круга)
изображены на рисунках 4.1 а,б,в.)
80
Определение. L-многогранником^ или многогранником Делоне
(го, Яо)"системы L С Еп называется выпуклый п-мерный многогранник
Р с вершинами в точках системы L = {Ц}, обладающий следующими
двумя свойствами:
1)	Вокруг многогранника Р можно описать шар Cl(v,p) конечного
радиуса р > 0 (то есть существует шар, на поверхности которого лежат
все вершины многогранника Р).
2)	Внутри и на поверхности шара £1(у,р) нет других точек систе-
мы L = {Ц}, кроме вершин многогранника Р, то есть открытый шар
int Cl(v,p) является стационарным пустым шаром системы L = {Ц} (см.
рис. 4.1 в - шар с центром «2- а также упражнение 4 к §2).
Из определения L-многогранника (го, Ро)"системы следует, что ра-
диус р описанного вокруг любого L-многогранника шара удовлетворяет
неравенству:
р < Ро,
где Rq - радиус равномерности системы L = {Ц}.
Наше дальнейшее исследование будет направлено на доказательство
того, что множество L-многогранников (как и множество многогранни-
ков Дирихле-Вороного) образует нормальное разбиение пространства Еп
(L-разбиение) и что эти два разбиения комбинаторно двойственны.
Упражнение 4.1. Покажите, что при выполнении алгоритма, на-
зываемого методом пустого шара для любой точки I (г, Я)-системы L,
попадающей на поверхность пустого шара, центр этого шара, начиная
с момента касания точки I все время находится в пределах области
Дирихле-Вороного точки Г, а в конечный момент попадает в пересечение
областей Д-В всех точек, лежащих на пустом стационарном шаре.
2.	Степень точки относительно сферы
Во многих дальнейших рассуждениях ключевая роль будет отведена
следующему простому понятию.
Степенью точки х относительно (замкнутого) шара Q(a, 7?) с цент-
ром а и радиусом R (или относительно сферы 5(а,Я)) называют ве-
щественную функцию Ф : Еп —> R, определенную формулой (см. рис.
4.2 а)
Фс>(ж) = \х — а|2 — R2.	(4-1)
81
Очевидно, что степень точки х принимает положительные, нулевые
и отрицательные значения соответственно вне, на поверхности и внутри
шара Q(a, 7?) (а потому является критерием расположения точки отно-
сительно шара).
Упражнение 4.2. Пусть I и т - прямые, проходящие через точ-
ку X, причем I пересекает сферу S(a,R) в двух точках У1,У2, a m -
касается сферы в точке Z. Докажите, что степень точки X относитель-
но сферы S(a,R) также может быть вычислена по формулам 4>q(X) =
= |ХУ1|-|ХУ2| = \XZ\2 (см. рис. 4.2 6). (Указание: решить планиметри-
ческую задачу, рассмотрев сечение двумерной плоскостью, проходящей
через точки А,Х и У1,У2 (либо Z).)
3.	Комментарии к методу ’’пустого шара”
Этот пункт целиком посвящен комментариям, дающим строгое и
подробное аналитическое изложение метода Б.Н.Делоне пустого шара,
приведенного в первом пункте. Читатель, хорошо подготовленный в об-
ласти n-мерной евклидовой геометрии, может пропустить ниже следу-
ющий материал при первом чтении.
Первый этап алгоритма Делоне - расширение пустого шара с фикси-
рованным центром ао от точки до столкновения с точками из (го,Яо)-
системы L - может быть объяснен предложением 3.1 о существовании
конечной подсистемы {Ц} ближайших к ао точек множества L, то есть
о существовании пустого шара Q(ao,Po)5 содержащего точки {Ц} на сво-
ей поверхности. (Для практического разыскания р следует например
взять	— а0|} Для всех точек Ц Е L, лежащих в непустом шаре
Q(ao,Ro), гДе - радиус дискретности.)
Для разъяснения второго и последующих шагов алгоритма Дело-
не введем следующие обозначения. Пусть Q(ao,p) _ пустой шар, со-
82
держащий на поверхности А:-мерный комплекс точек {Zi,... , С L
(О < к < п — 1), определяющих А:-мерную плоскость Рк (см. рис. 4.3).
Тогда центр ао лежит в (п — &)-мерной плоскости Рп~к точек простран-
ства, равноудаленных от точек Z"i,..., 1т (см. лемму 1.2 § 1 этой главы).
Плоскости Рк и Рп~к ортогонально дополнительны и пересекаются в
единственной точке й - центре А:-мерной сферы Sk(u, содержащей
точки Г1,..., 1т (и однозначно ими определяемой).
Рассмотрим сначала случай, когда ао не лежит в плоскости Рк, то
есть qq й. Пусть р1 - прямая, проходящая через точки й и ао, а
потому содержащаяся в эквидистанционной плоскости Рп~к. И пусть
П - ортогонально дополнительная к ней (п — 1)-плоскость, проходящая
через точку й, а потому содержащая плоскость Рк и точки 1±,... ,1т.
Введем координаты на прямой р1, выбрав нулевую точку й Е П и
некоторый эталон единичной длины. Положительное направление для
дальнейшего удобно выбрать произвольно и независимо от расположе-
ния точек ао и й. Открытое полупространство, ограниченное гипер-
плоскостью П и соответствующее положительному направлению оси
назовем тг+, а противоположное ему открытое полупространство - 7г-.
Обозначим через ао координату точки ао на прямой р1. Она равна рас-
стоянию |а0 — й\, взятому со знаком плюс, если ао Е тг+, и минус, если
ао Е тг~. (См. на рис. 4.3 точки ао и а'о соответственно. Числовые коор-
динаты точек всюду на рис. 4.3 обозначены ниже прямой р1, а названия
точек - выше.)
Любую точку Ц системы L будем характеризовать двумя величи-
нами: 7^ -расстоянием от точки Ц до прямой р1 (равной длине отрезка
где Ц - ортогональная проекция точки Ц на прямую р1^, и Xi -
величиной направленного отрезка [й, /'] (то есть координатой точки
на прямой р1).
Заставим теперь точку ао передвигаться по прямой р1 в положи-
тельную сторону (на рис. 4.3 вправо), одновременно изменяя (увеличи-
вая или уменьшая) радиус шара так, чтобы он все время содержал точки
fi,... ,1т. Для этого обозначим pt - центр и радиус подвижного шара
и положим
/ .	t \ _ t
at = I 1----]и -I--ао, t E (—oo, oo).
\	Q() /	«0
Очевидно, что при таком определении (для любого t Е R) точка at лежит
на прямой р1, а число t представляет ее координату на оси р1, поскольку
(at — и) =	— й), и \at — й\ = |^-| • |сщ| = И- Названному выше
движению точки at соответствует увеличение параметра t начиная со
значения t = <т0, при котором at = ао- (Отметим также, что at = й при
t = 0.)
(В случае, когда первоначальный центр ао пустого шара лежит в
плоскости Рк (то есть ао = й), следует определить прямую р1 соотно-
шением
at = ао + t • е, t Е R,,
где ё - произвольный единичный вектор, ортогональный плоскости
Рк, и положить ао = 0.)
Радиус подвижного шара изменяется в соответствии с формулой
Pt — fat ~h)2 — (at — й)2 + (й — fi)2 = t2 + $q2-
Очевидно, что квадрат расстояния от центра at подвижной сферы
до фиксированной точки Ц Е L есть величина
(ч G't) — (ч f'i) “Ь (ч	“Ь t) -
Итак, степень фиксированной точки Ц относительно ’’раздувающегося”
(или ’’сдувающегося”) шара Q(at,pt) есть функция
<?*(*) = (Ji ~at)2 - Pt = H + (Ai - t)2] - [t2 + <5g],
которая после несложных преобразований принимает вид:
^(t) = -(2Ai)-t+[U2 + An-<502]-
График этой линейной (!) функции изображен на рисунках 4.4 а,б.
Условие пустоты первоначального расположения сферы Q(do,p) оз-
начает, что ^(^о) > 0- (Заметим также, что степень ipt (o) = U2 + AD-
—8q точки Ц относительно сферы fl(at, pt) |t=o =	положительна
лишь когда Ц Q(u, Jo)-)
Монотонное возрастание [соответственно убывание] функции <^(t)
эквивалентно условию А^ < О [соответственно А? >0], то есть располо-
жению точки Ц в отрицательном полупространстве 7г- [сответственно в
положительном полупространстве тг+]. Таким образом, точки Ц, лежа-
щие в отрицательном полупространстве 7г-, не попадают в исследуемый
подвижный шар (поскольку > 0 при t > см. рис. 4.4 а). Точки,
лежащие в гиперплоскости П (А* = 0), имеют постоянную (не отрица-
тельную) степень относительно подвижного шара
А для точек Ц из полупространства тг+ значение t = ti > при
котором ее функция обращается в ноль (рис. 4.4 б) задается фор-
мулой
,	(7? + AD-d02
’	2  Xi
что соответствует ожидаемому попаданию фиксированной точки
Ц Е 7г+ на ’’раздувающуюся” сферу Sk(at,pt). Очевидно, что каждая
точка Ц системы L, лежащая в полупространстве тг+, задает подобную
функцию и соответствующее значение ’’попадания” tj. при кото-
ром = 0.
Для отыскания комплекса точек, на которые первыми натолкнется
раздувающийся пустой шар flt(at,pt) следует выбрать из точек Ц Е тг+
подмножество, на котором достигается минимум из таких величин
Для этого достаточно проверить лишь точки Ц системы L, лежащие
в подвижном шаре flt(at,pt) при достижении им радиуса равномерности
85
pt = Ро системы L (то есть при t = t0, удовлетворяющем уравнению
Pt = Ro ~ t2 + 6% = R$).
Действительно, для точек Ц Е тг+, лежащих вне шара	Ro)
выполнено неравенство ^(^о) > 0, а потому (в силу монотонного убы-
вания функции рДД)) и неравенство ti > to, в то время как точки Ц,
лежащие в шаре Qto(ato,Ro) удовлетворяют неравенству ^(^о) < 0 и
ti < to-
Таким образом, рассмотрен один шаг алгоритма Делоне (метода
пустого шара), увеличивающий по меньшей мере на единицу размер-
ность к комплекса точек {Ц}, лежащих на поверхности пустого подвиж-
ного шара Q(d,p). Применение конечного числа таких шагов, очевидно,
дает п-мерный комплекс точек Ц Е L, расположенных на пустом стацио-
нарном шаре Q(d,p), введенном в определении L-многогоранника (см.
п.1).
Заметим, что произвольность в выборе положительного направле-
ния на оси р1 (то есть направления движения центра шара) показывает,
что движение пустого шара (при размерности системы к > 1) можно с
тем же успехом осуществлять и в сторону первоначального уменьшения
радиуса (см. рисунок 4.1 в, либо точку а'о на рис. 4.3).
4.	Существование L-многогранника (г, Р)-системы
Непосредственным следствием метода пустого шара является
Предложение 4.1. Для любой (г, R)-системы существует хотя бы
один L-многогранник. > •
Представленные далее связи понятия L-многогранника с разбие-
нием Дирихле-Вороного дают более полное представление о центрах
L-многогранников.
Предложение 4.2. Множество {й,} центров шаров, описанных во-
круг L-многранников (г, R)-системы L = {Ц}, совпадает с множеством
V = V(0) вершин разбиения Дирихле-Вороного этой системы.
> Вершина Vj разбиения Д-В является центром шара, описанного
вокруг множества ближайших к ней точек (г, Р)-системы L = {Ц},
причем dimZ^ = п (см. предложение 3.11 § 3 и его следствие). Поэтому
их выпуклая оболочка convZ^, очевидно, является L-многогранником.
Обратно, центр Vj шара, описанного вокруг L-многогранника Р,
имеет n-мерную систему extP вершин L-многогранника Р в качестве
полного множества ближайших точек системы L = {Ц}, а потому
86
является вершиной разбиения Д-В (см. предложение 3.10 § 3). •
В дальнейшем £(й/) будет обозначать L-многогранник с центром
описанного шара в вершине Vj разбиения Д-В.
Заметим, что вершины extP =	= {lig}^=i L-многогранника £(vj)
представляют собой центры многогранников Д-В V(Zzi)? • •	кото-
рые содержат вершину Vj (см. предложение 3.11 § 3) и Vj =	У(/гд)-
Таким образом, может быть дано другое эквивалентное определение L-
многогранника.
L-многогранником (г, R)-системы L = {Ц} называется выпуклая
оболочка множества {lig}^=i С L всех тех точек системы L, области Д-В
которых имеют в качестве общего пересечения одну из вершин разбие-
ния Дирихле-Вороного.
Из этих замечаний следует, что множество L-многогранников од-
нозначно задается (г, Р)-системой L = {Ц}, поскольку однозначность
разбиения Д-В не вызывает сомнений.
5.	Лемма о шапочках пересекающихся шаров
Лемма 4.3 (о ’’шапочках” пересекающихся шаров).
Пусть Qi = Q(cTi,Pi); Q2 = Q (02,^2) - два замкнутых шара с центра-
ми а± Й2 и радиусами ERR2; и Si, S2 - сферы, ограничивающие эти
шары.
Если сферы Si, S2 имеют непустое, отличное от точки пересече-
ние Si A S2, то оно представляет собой (п — V)-мерную сферу, лежащую
в гиперплоскости П, перпендикулярной прямой aff{ai,a2}.
Пусть 7Г1 - открытое полупространство, ограниченное гиперплос-
костью П и содержащее конец вектора аДа^, приложенного к любой точ-
ке плоскости П (см. рис. 4-5), а тм - ему противоположное открытое
полупространство. Тогда 1) полупространство 7Г1, гиперплоскость П,
полупространство 7Г2 задаются равенством и неравенствами
(7Г1 :) Ф1(ж) < Ф2(ж), (П :) Ф1(ж) = Ф2(ж), (тг2 :) Ф1(^) > Ф2(^);
2) справедливы строгие включения:
int Qi А яд D Q2 А 7Г1
Q1 А 7Г2 с int Q2 А 7Г2-
(Другими словами, в полупространстве тц, сонаправленном вектору
ajai, шапочка одноименного шара Qi содержит шапочку другого шара Qj
(где {г,7} = {1,2}). И, в частности, в полупространстве, содержащем
центр большего шара, шапочка большего шара содержит шапочку мень-
шего шара, а в противоположном полупространстве шапочки подчинены
Фх(ж) < Ф2(ж)	(4.2)
(как легко видеть при подстановке) задает полупространство
7Г1 : 2ж • (й2 - ai) < (-Rj -+ (й! - й1),	(4.2)'
ограниченное гиперплоскостью
П: Фх(ж) = Ф2(ж) (или 2х • (а2 — ах) = (R^ — R%) + (а^ — а^)), (4.3)
которая, очевидно, содержит пересечение сфер Si и S2, задаваемое сис-
темой
Ф1(ж) = 0, Ф2(ж) = 0.
Из уравнения гиперплоскости П следует, что П перпендикулярна пря-
мой aff{ax,a2}. Кроме того, если - произвольная точка плоскости
П, то есть удовлетворяет уравнению (4.3), то точка х = xq + а2ах =
= xq + (ai — a2) (полученная сдвигом на вектор а2ах) лежит в полу-
пространстве 7Г1, поскольку удовлетворяет задающему его неравенству
(4.2)’ (так как (ах — а2)(а2 — ах) < 0).
Чтобы доказать включения, возьмем произвольную точку
х Е (Q2 П 7Г1). Для нее выполнены неравенства Ф1(ж) < Ф2СЁ) и
Ф2(ж) < 0, а значит Ф1(ж) < 0. Поэтому х Е int Qi A tti .
Неравенство, противоположное (4.2), задает противоположное полу-
пространство 7Г2, в котором аналогично доказывается противоположное
включение.
Предположим теперь, что R\ > R>. Покажем, что а\ Е tti. Дей-
ствительно, Ф1(ах) = (ai — Й1)2 — Rl = —Я2, $2(^1) = (<й — Й2)2 — R2,
откуда Ф1(й1) —Ф2(ах) = — (Rl — R%) — (ai — Й2)2 < 0, поскольку R± > R2,
и fli a2. Следовательно, Ф1(й1) < Ф2(<й)- •
6.	Нормальная упаковка L-многогранников. Свойства граней
Первым применением леммы о ’’шапочках пересекающихся шаров”
будет доказательство нормальности пересечения L-многогранников.
Пусть £(vt) и ~ два L-многогранника (го, Яо)"системы
L = {Ц} с центрами Vi,Vj, имеющие непустое пересечение. И пусть
Qj = Qj (vj, Rj) - описанные вокруг них замкнутые ша-
ры; Si и Sj - ограничивающие их сферы, Sn-1 - (п — 1)-мерная сфера,
полученная пересечением Si A S'?, и П - содержащая ее гиперплоскость.
Предложение 4.4. В приведённых выше обозначениях L-многогран-
ники £(vi) и расположены в разных замкнутых полупространст-
вах, определяемых гиперплоскостью П. Если пересечение A
L-многогранников непусто, то оно является целой гранью некоторой
размерности к (0 < к < п — 1) обоих многогранников (см. рис. 4-6)-
> Из условия пустоты шара Qj следует, что вершины ext £(vi) L-
многогранника £(vi), будучи точками системы L = {Ц}, не могут ле-
89
жать в том открытом полупространстве (ограниченном плоскостью П),
где шапочка шара Qi содержится в открытом пустом шаре intQj. Ана-
логично, вершины не могут содержаться в противоположном от-
крытом полупространстве. Поэтому L-многогранники £(yi) и £(йД яв-
ляясь выпуклыми оболочками своих вершин, лежат в противоположных
замкнутых полупространствах.
Очевидно, что (п — 1)-мерная сфера Sn-1 пересечения сфер Si и S2
может быть получена пересечением Sn-1 = Si А П = S3; А П. Поэтому
множество {^ } точек (го, Яо)"системы Ь, попавших на
(п — 1)-мерную сферу Sn-1, представляет собой множество всех вершин
L-многогранника £(vi), лежащих в опорной для него гиперплоскости П
(а так же совпадает и с множеством вершин другого L-многогранника
£(й/), лежащих в П). Поэтому их выпуклая оболочка Q = conv{^q} яв-
ляется гранью для L-многогранника £(vi), отсеченной плоскостью П :
Q = £(щ) А П (аналогично Q = £(vj) А П также является гранью 2-го
L-многогранника £(й,-)).
С другой стороны, £(щ) A £(vj) С П и потому грань
Q = £(vi) А П = £(vj) А П = £(vi) A £(vj) И П = £(щ) A £(vj) и есть
искомое пересечение L-многогранников. •
Представленное в доказательстве строение грани Q можно обоб-
щить следующим замечанием. Известно свойство выпуклых многогран-
ников о том, что любая А:-мерная грань Q n-мерного многогранника Р
(к < п) может быть получена пересечением тг& А Р = Q А:-мерной плос-
кости 7ц. с многогранником Р. А вершины грани Q есть в точности
вершины многогранника Р, лежащие в плоскости 7ц. (см. рис. 4.7).
Легко также видеть, что непустое отличное от точки сечение
90
n-мерной сферы Sn(a,p) шара Qn(n,p) А:-мерной плоскостью тгк пред-
ставляет собой А:-мерную сферу Sk(u, 6) шар Qk(u, 6) , центр й которой
есть ортогональная проекция центра а n-мерной сферы на плоскость тгк.
А радиусы связаны соотношением р2 = S2 + |а — п|2. (Проверьте!)
Отсюда следует, что каждая из А:-мерных (1 < к < п) граней
L-многогранника обладает свойствами, аналогичными свойствам само-
го L-многогранника:
1) вокруг грани можно описать расположенный в заданной гранью
плоскости А:-мерный шар Qk (см. рис. 4.7);
2) замкнутый шар Qk не содержит, кроме вершин грани, никаких
других точек системы L.
Свойства граней продолжает развивать следующее предложение.
Предложение 4.5. Каждый L - многогранник £(vt)	систе-
мы L = {Ц} по каждой своей гиперграни Q смежен с некоторым другим
L-многогранником	то есть Q = £(vt) V\£(vj') — их общая гипер-
гранъ.
> Обозначим _ шар, описанный вокруг L-многогранника £(vi).
Пусть й - центр (п — 1)-мерной сферы Sn-1, описанной вокруг вер-
шин (п — 1)-грани Q, которая лежит в опорной для многогранника £(vt)
гиперплоскости П (см. рис. 4.8). Обозначим ё - единичный век-
тор нормали к плоскости П, направленный в ограниченное ею откры-
тое полупространство тг+, не содержащее точек L-многогранника
(Соответственно £(щ) С тг~; см. рис. 4.8.) И пусть р1 — прямая,
проведенная через точки щ и й — множество точек пространства, рав-
ноудаленных от вершин грани Q (см. лемму 1.2 § 1 этой главы). Как
следствие р1 || ё.
91
Воспользуемся вновь идеей метода пустого шара, описанного в
пунктах 1 и 3. Будем смещать центр щ шара вдоль прямой р1 в
сторону полупространства тг+, не содержащего многогранника £(щ), из-
меняя радиус так, чтобы шар все время проходил через вершины грани
Q. При этом шар ’’сразу оторвется” от всех вершин, лежащих в по-
лупространстве 7г- (то есть всех вершин L-многогранника £(щ) кроме
вершин грани Q), и через ’’некоторое время” наткнется на некоторые
точки {Zjfe} (г, Я)-системы L в полупространстве тг+, образуя новый
L-многогранник £(vj).
Действительно, следуя пункту 3, положим
Vt = Щ + t • е, t Е R.
Тогда для любого сколь угодно малого числа t > 0 шапочка подвижно-
го шара	лежащая в полупространстве 7г- в силу леммы 4.3
(о шапочках пересекающихся шаров) лежит внутри шара Qi. описан-
ного вокруг исходного L-многогранника £(щ) (рис. 4.8).
Как показывают рассмотрения пункта 3, число точек {Zjfe}
(г, Я)-системы L из открытого полупространства тг+, на которые первы-
ми наткнется подвижный шар Qt(vt,pt) конечно. Очевидно, что их сте-
пени pjk (t) относительно этого шара (см. п.З) — непрерывные монотон-
но убывающие функции, имеющие положительные значения при t = О
(поскольку ljk £ Q^. Поэтому найдется такое (достаточно малое) зна-
чение > 0 параметра t, что соответствующий шар Q* = Qt* (^, pt*)
не содержит других точек (г, Я)-системы L кроме вершин грани Q (ле-
жащих на его поверхности).
Попадая в условия пункта 3, обозначим Vj конечную точку движе-
ния центра Это центр пустого стационарного шара Qj, a £(vj) —
соответствующий L-многогранник. Поскольку пересечение сфер, опи-
санных вокруг L-многогранников £(щ), £(vj) есть (п — 1)-мерная сфера
Sn-1, описанная вокруг гиперграни Q, то, как следует из доказательст-
ва предложения 4.4, £(щ) A £(vj) = Q — их общая гипергрань. •
На самом деле отрезок [vi,Vj], вдоль которого двигался центр vt пус-
того подвижного шара, есть не что иное как ребро разбиения Дирихле-
Вороного (для всех Д-В многогранников У(Цг),... ,V(l{m) с центрами в
вершинах гиперграни Q).
92
Действительно, используя идею доказательства предложения 3.9 §3
настоящей главы, легко видеть, что вокруг центра щ L-многогранника
£(^г) существует ^-окрестность U£(vt), для каждой точки х которой
сохраняют свою силу неравенства
11
ч
рис. 4.8), найдется точка и*,
пространства тг+ такая, что шар Q* = Q(i;*,
выполненные для х = щ.
На интервале (^1,^2) = U£(vt) Ар1, полученном пересечением е-
окрестности U£(vt) точки щ и проходящей через нее прямой р1 (см.
смещенная от щ в сторону ’’пустого” полу-
щ — lir ), содержащий на по-
верхности вершины грани Q, не содержит других точек (г, Я)-системы
L (лемма о шапочках шаров). Следовательно (п —1)-мерная система вер-
шин грани Q образует полный набор ближайших точек (г, Я)-системы
L для центра v*. А сама точка v* — относительно внутренняя для реб-
ра (1-грани) разбиения Дирихле-Вороного, лежащего на прямой р1 (см.
предл. 3.10 § 3 этой главы). Один из концов этого ребра — точка щ, а
другой — очевидно полученная в доказательстве точка Vj.
Отметим, что для размерностей п = 2 и п = 3 пространства из от-
веченного утверждением 4.5 свойства любого L-многогранника иметь
межный L-многогранник по каждой своей гиперграни, почти очевидно
вытекает, что L-многогранники образуют покрытие пространства, по-
кольку любые пустоты должны были бы иметь ’’стенки” размерности
п — 1). Для произвольной размерности это свойство подробно доказано
; пункте 7.
Идею доказательства последнего предложения можно использовать,
выведя еще одно очень важное свойство граней L-многогранников.
Предложение 4.6. Конечное подмножество	точек
r\R)-системы L = {Ц} тогда и только тогда представляет полное
тожество вершин грани некоторого L-многогранника, когда найдется
густой шар Q(cup), не содержащий точек системы L кроме точек мно-
жества	лежащих на его поверхности; то есть найдется точка
гространства а, для которой {/гд}^=1 — полное множество ближайших
почек (г,К)-системы L.
> Необходимость. Пусть {Цг,..., Цт } - множество вершин
^-мерной грани Q (0 < k < п — 1) L-многогранника £(v). И пусть П - ги-
93
перплоскость, отсекающая грань Q от многогранника £(v)
(Q = П А £(£)), а следовательно отделяющая и ее вершины. (Другими
словами вершины {/гд}^=1 грани Q лежат в гиперплоскости П, а осталь-
ные вершины L-многогранника £(ё) - в ограниченном ею открытом по-
лупространстве 7г-). Обозначим наконец ё - внешнюю по отношению к
многограннику £(ё) единичную нормаль к (п — 1)-плоскости П (направ-
ленную в полупространство 7Г+).
а)
Рис. 4.9
б)
Следует, как и в предложении 4.5, ’’слегка сдвинуть” центр ша-
ра Q(i;,po) (описанного вокруг L-многогранника £(йУ) в направлении
вектора ё, оставляя его проходящим через вершины {lig}^=i грани Q.
Тогда, не встретив еще новых точек системы L в полупространстве
7г+ пустой шар Q(a, р) покинет все вершины L-многогранника £(v) в
полупространстве 7г-, оставляя на своей поверхности только вершины
грани Q. Отличие в доказательстве с предложением 4.5 состоит в том,
что вектор ё, приложенный к центру L-многогранника v не всегда мо-
жет быть направлен в центр й А:-мерного шара, описанного вокруг грани
Q (примером служит ребро [Zi, Z2] трехмерного L-симплекса
на рис. 4.9, где ё |/w).
Достаточность. Пусть Q(a, р) - пустой шар, содержащий на своей
поверхности лишь множество {iig}^=i точек (г, Я)—системы L. Если
начать расширять этот пустой шар, отталкиваясь от точек	то
есть начать с этой исходной позиции выполнение алгоритма нахождения
L-многогранника методом Делоне пустого ’’раздувающегося” шара, то
получим в результате L-многогранник £(v), в число вершин которого
входят все точки {Г^,..., lim }.
Заметим, что каждый этап алгоритма увеличивает число (и размер-
ность) точек (г, Я)-системы, находящихся на пустом подвижном шаре.
А если перейти к выпуклым оболочкам этих множеств, получим конеч-
ную последовательность многогранников Q = F± □ F2 □ ... □ Fp =
= £(v), первый из которых Q - это А:-мерная выпуклая оболочка мно-
жества точек	а последний — L-многогранник £(v). Причем
каждый последующий содержит предыдущий в качестве собственной
грани (которая отсекается соответствующей этапу алгоритма гипер-
плоскостью П, см. комментарии в п.З). Пользуясь теоремой 1.6 § 1
гл.2, заключаем, что Q есть грань L-многогранника £(v). •
7.	Покрытие пространства L-многогранниками. L-разбиение
Прежде всего заметим, что семейство всех L-многрогранников
(го, Яо)"системы L = {Ц} является локально конечным. Действительно,
максимальное расстояние между точками L-многогранника не превы-
шает 2Rq (где Rq - радиус равномерности системы L). Поэтому любая
^-окрестность U£(xq) произвольной точки пространства xq пересекает-
ся лишь с L-многогранниками, лежащими в шаре Q(xo,2/?o + е). А их
вершины вместе с непересекающимися описанными вокруг них шара-
ми радиуса го/2 лежат в шаре Q(xo,2/?o + £ + го/2). Следовательно их
количество конечно.
Заметим теперь, что любой замкнутый шар Q пересекается лишь
с конечным числом множеств из произвольного локально конечного се-
мейства множеств {Mi}, поскольку любая точка шара обладает окрест-
ностью, которая пересекается с конечным числом множеств. Эти ок-
рестности образуют покрытие компакта Q, из которого может быть вы-
брано конечное подпокрытие, пересекающееся с конечным числом мно-
жеств Mi.
Лемма 4.7 (лемма ”о шашлыке”). Пусть {Pi} - локально конеч-
ная упаковка (см. п.1) п-мерных выпуклых конечногранных многогран-
ников в пространстве Еп, и Pr - один из них. Для любой внутренней
точки xq многогранника Pr и произвольной точки у Pr в любой е-
окрестности U£(xq) точки xq найдется точка х такая, что отрезок
[х,у] пересекает границы многогранников лишь по относительно внут-
ренним точкам граней размерности (п — 1). (То есть точку xq можно
слегка сдвинуть, чтобы отрезок [жо, у] не проходил через: вершины, реб-
ра, .. .,(п — 2)-грани многогранников.)
х=а1 Ъх	а3 Ъ3	а5 Ь5
I 9—------£/////j/////^	£//////q е
а2 ^2	а4	У
Рис. 4.10
>	Заметим прежде всего, что количество многогранников семейст-
ва {Р/}, которые могут иметь непустые пересечения с отрезками вида
[х,у] (х Е U£(xq)), конечно, поскольку все эти отрезки лежат в шаре
О(ж0, |®о - У| +£)•
Поскольку отрезок [х,у] и любой из многогранников Pi - выпук-
лые замкнутые ограниченные множества, то непустые пересечения
[х,у] А Р{к представляют собой компакты на прямой, то есть точки ли-
бо отрезки вида [ar,br], возможно имеющие совпадающие концы, но не
пересекающиеся по своим внутренним точкам (см. рис. 4.10).
Концы каждого отрезка [ar,br], очевидно, лежат на границе соот-
ветствующего L-многогранника Pir, а значит и на некоторой из его ги-
перграней. Для каждой точки аг [либо Ьг] плоскость содержащей ее
гиперграни Qr [Qr] может быть выбрана не параллельной отрезку [х,у]
(поскольку многогранник Pir получается пересечением замкнутых по-
лупространств, ограниченных гиперплоскостями своих гиперграней; и
в противном случае соответствующее полупространство содержит всю
прямую aff{x,y}, а мы можем перейти к другой гиперграни много-
гранника).
Предположим, что некоторая часть из точек ar,br лежит внутри
соответствующих гиперграней многогранников Pir (и тогда аг 7^ Ьг -
будем назвать их в доказательстве ’’внутренними”). И хотя бы одна
точка (пусть aj) - на границе соответствующей гиперграни Qj много-
гранника Pjj •
96
Покажем,что смещением точки х на сколь угодно малую величину
6 > 0 можно, сохранив все ’’внутренние” точки, добавить к их числу
и точку aj. Действительно, вокруг каждой внутренней точки аг [или
Ьг] может быть описан (п — 1)-мерный открытый шар О™-1, целиком
лежащий в соответствующей гиперграни Qir [соответственно Qir]. Его
праобраз при центральной проекции с центром у (то есть множество
лучей (y,z), z Е О™-1) есть открытый конус (см. приложение 1 к гл.З).
Пересечение (конечного числа) всех этих конусов есть открытая окрест-
ность U(x) ТОЧКИ X.
А на гиперграни Qj. содержащей на своей относительной границе
точку aj в силу теоремы 3.2 гл.1 найдется полуинтервал [zq, aj), целиком
лежащий в относительной внутренности гиперграни Qj. Его праобраз
при центральной проекции с центром у - это часть двумерной полуплос-
кости 7г^_, проходящей своей границей через точки aj и х. Пересечение
7г^_ A U(x) с J-окрестностью точки х и есть множество искомых точек
ж', куда следует переместить точку х.
В силу ограниченности количества многогранников системы {Pj},
которые могут иметь непустое пересечение с отрезками [у,х\, при по-
вторении конечного числа раз описанной процедуры получим, что все
точки ar,br на отрезке [х,у] - ’’внутренние”. В силу произвольности
выбора 6 > 0 это означает выполнение требования леммы. •
Предложение 4.8. Если непустое семейство Pi п-мерных конечно-
гранных выпуклых многогранников образует локально-конечную упаковку
в пространстве Еп и любой из них по каждой своей (п — Р)-грани смежен
с другим многогранником семейства, то многогранники семейства {Pi}
образуют покрытие пространства Еп.
>	Покажем, что для любой точки у пространства Еп найдется со-
держащий ее многогранник семейства {Р*}. Зафиксируем некоторый
многогранник Рд. этого семейства и произвольную внутреннюю точку
xq в нем. В силу предложениея 4.7 в любой ^-окрестности точки xq най-
дется точка х такая, что отрезок [ж, у] пересекает границы многогранни-
ков {Pi} лишь по относительно внутренним точкам их (п — 1)-граней;
и по свойству смежности выходя из одного многогранника, одновре-
менно входит в следующий (см. рис. 4.11). Другими словами отрезки
[ar,5r] = [х,у] С\ Pir ненулевых пересечений сегмента [х,у] с многогран-
никами семейства {Pi} образуют разбиение отрезка [х,у] на частичные
отрезки [5r-i, Ьг] (г = 1,..., Q, 6о = х, bq = у), последний из которых
97
X	\а,	\а 4	У \
•—	
а3	b\	/ а3	а5	Ь5 \
X=bo bx	b2	b} b4 b5-y
Puc. 4.11
\bq_i, у] содержит на конце точку у и представляет содержащий ее мно-
гогранник Piq Е {Р*}. •
Поскольку, как было сказано в предложении 4.6, каждый L-много-
гранник (г, Р)-системы по каждой своей гиперграни смежен с другим
L-многогранником, то в совокупности они образуют покрытие прост-
ранства Еп, и учитывая, что пересечения L-многогранников представ-
ляют их целые грани (предл. 4.6), доказана
Теорема 4.9. L-многогранники любой (г, R)-системы образуют нор-
мальное разбиение пространства Еп. > •
Определение. Нормальное разбиение пространства Еп на L-mho-
гогранники, заданное (г, Р)-системой L = {Ц}, называют L-разбиением.
Следствие. L-разбиение любой (г, Р)-системы L = {Ц} единствен-
но, то есть задается ею однозначно.
>	(Доказательство можно провести независимо от разбиения Ди-
рихле-Вороного, в отличие от сделанного в п.4.) Пусть Р = {Р^} и
Р' = {PJ} - два L-разбиения, заданные (г, Я)-системой L = {Ц}. И -
произвольный L-многогранник первого разбиения. Поскольку все пере-
сечения L-многогранника Р^ с L-многогранниками второй системы Р'
представляют грани многогранника Рд.. а система Pf = {PJ} составляет
покрытие пространства, то найдется многогранник Р' Е Р', совпадаю-
щий с многогранником Рд.. •
8.	Необходимые и достаточные условия для L-разбиения
На практике при отыскании L-разбиения конкретной (г, Р)-системы
L = {Ц} для найденных многогранников с вершинами в точках систе-
98
мы, вокруг которых может быть описан шар, бывает трудным прове-
рить пустоту этого шара. Однако, как будет показано в этом пункте,
для установления того, что найдено именно L-разбиение, достаточно
проверить, что вершины смежных многогранников к любому данному
многограннику не лежат в описанном вокруг него шаре.
Лемма 4.10 (основная лемма о L-разбиениях). Пусть L = {Ц}
- некоторая (г, R)-система, и задано нормальное разбиение Р = {Pj}
пространства Еп на выпуклые п-мерные конечногранные многогранники,
все вершины которых - точки системы L, и любая точка этой системы
- вершина этого разбиения.
Необходимые и достаточные условия того, что разбиение Р = {Р/}
является L-разбиением состоит в том, что
1) каждый многогранник Pj Е Р может быть вписан в шар (содержащий
все вершины многогранника);
2) у каждой пары многогранников системы Р, смежных по (п — 1)-мерной
грани, вершины одного, не лежащие в их общей грани, не лежат в шаре,
описанном вокруг другого, и обратно.
Рис. 4.12
> Неоходимость этих условий очевидна. Докажем достаточность.
Обозначим (Pj) - шары, описанные вокруг многогранников Pj. Возь-
мем произвольный многогранник разбиения Р = {Pj}, обозначив его
Ро и докажем пустоту описанного вокруг него шара (Ро), показав, что
произвольная фиксированная точка I (г, Р)-системы L лежит вне этого
шара.
В силу леммы 4.7 (”о шашлыке”) в многограннике Ро можно вы-
брать внутреннюю точку х так, что отрезок [х, I] пересекает много-
гранники Pj разбиения Р лишь по относительно внутренним точкам их
99
(n — 1)-граней и разбивается на конечное число частичных отрезков,
входящих в соответствующие многогранники Pj (см. рис. 4.12).
Обозначим Ро, Р±,..., Рт - многогранники системы Р = {Pj}, пере-
секаемые отрезком [ж, I] в порядке их расположения на нем, a (Pq), (Pi),
..., (Pm) - описанные вокруг них шары. Тогда точка I очевидно явля-
ется вершиной многогранника Рт.
Обозначая ту - степень точки I относительно многогранника Рд.
(А; = 0,1,..., ш), видим, что тт = 0. Кроме того степень точки I от-
носительно любых двух соседних многогранников P^,P^+i этой серии
(А; = 0,..., т — 1) подчинены неравенству ту >
Действительно, обозначим Щ — (п — 1)-мерную плоскость, задан-
ную общей гипергранью Q многогранников Рд. и Р&+1 и проходящую
через (п — 1)-мерное пересечение соответствующих сфер (P^),(P^+i).
Обозначая - ограниченное ею полупространство, содержащее точку
I (а х е тГдТ), видим, что Рд. С 7ГдГ, Р^+1 С 7г^. Тогда в полупростран-
стве 7г^ шапочка шара (P^+i) содержит шапочку шара (Pfc), а полупро-
странстве тг^ наоборот (см. лемму 4.3 о шапочках шаров), поскольку
противоположное включение означало бы, что вершины многогранника
Р&+1 лежат внутри шара (Р^). Поэтому и степени любой фиксированной
точки полупространства и в частности точки I подчинены неравен-
ству Tk > (см. доказательство леммы о шапочках пересекающихся
шаров).
Итак, справедлива система условий
То > Т1 >
Тт — 1
Р Тщ — о,
откуда следует, что степень то точки I относительно шара (Pq) описан-
ного вокруг многогранника Pq строго положительна, то есть точка I
лежит вне этого шара. •
§ 5. Двойственность разбиения Дирихле-Вороного
и L-разбиения (разбиения Делоне)
Напомним, что в параграфах 3, 4 (а также и здесь) зафиксирована
одна и та же произвольная (г, Р)-система L = {Ц}.
В параграфах 3 и 4 мы уже видели, что любой точке Ц (r,R)-
системы L (то есть вершине или 0-грани L-разбиения) соответствует
100
определенный ею n-мерный многогранник Дирихле-Вороного V(/J —
область движения центра пустого шара, опирающегося на точку Ц. Ана-
логичным образом в предложении 4.2 отмечено, что любому п-мерному
L-многограннику соответствует вершина (0-грань) v - центр пустого
стационарного шара, описанного вокруг вершин L-многогранника. Да-
лее, любой (п — 1)-грани L-разбиения, по которой смежны некоторые
L-многогранники £(уь) и £(vm) соответствует ребро (1-грань)
разбиения Д-В - путь центра пустого шара, опирающегося на вершины
(п — 1)-грани. Далее мы продолжим эти соответствия.
Зафиксируем произвольное конечное подмножество	точек
(г, Я)-системы L = {Ц}. Сравнивая для него критерий образования пол-
ного множества вершин некоторой L-грани (предложение 4.6) и крите-
рий максимальной образующей системы для грани Д-В (теорема 3.12),
видим, что они совпадают. (Это существование пустого шара, содержа-
щего на поверхности лишь точки	из L.) Таким образом эти два
семейства конечных подмножеств (г, Я)-системы L совпадают. Однако,
как показывает предложение 3.11, между максимальными образующи-
ми системами и гранями Д-В также существует взаимно-однозначное
соответствие.
Таким образом между гранями L-разбиения и гранями разбиения
Д-В фактически установлено взаимно-однозначное соответствие, кото-
рое можно выразить диаграммой, изображенной на рисунке 5.1.
L-грань
Множество
вершин L-грани
Максимальная
образующая система
точек (г,К)-системы
для грани Д-В
> W
Грань Д-В
Рис 5.1
Будем называть L-грань и грань Д-В, поставленные таким образом
друг другу в соответствие - двойственными.
(Напомним, что Д-В грань W определяется как множество точек
пространства, для которых точки	(г, Я)-системы L являются
одновременно ближайшими, то есть это область движения пустого шара,
опирающегося своей поверхностью на точки
Тоже соответствие между гранями Д-В и L-гранями можно осу-
ществить через посредство вершин грани Д-В, введя для L-грани кон-
струкцию, аналогичную максимальной образующей системе для грани
Д-В.
Действительно, любая А:-мерная грань Q (0 < к < п — 1) L-много-
гранника £(i?o) может быть представлена пересечением Q = Пр=1 Gp
набора Gi,... некоторых из его (п — 1)-граней. А каждая из этих
граней - пересечением Gp = £(^о) П многогранника £(i?o) с соот-
ветствующим смежным L-многогранником £(ур). Следовательно любая
А:-мерная грань Q L-разбиения (0 < к < п — 1) может быть представ-
лена пересечением Q = П^=о £(йр) некоторого числа L-многогранников.
Поэтому корректно следующее определение.
Определение. Для любой данной L-грани Q система ш = {vjk}P=1
вершин разбиения Д-В (то есть центров шаров, описанных вокруг
L-многогранников), удовлетворяющая условию Q = £(vjk) и со-
держащая всякую другую систему вершин разбиения Д-В, удовлетво-
ряющую этому условию, называется максимальной маркирующей сис-
темой L-грани Q и будет обозначаться Vq.
Очевидно, что в максимальную маркирующую систему входят те
и только те вершины v разбиения Д-В, L-многогранники £(Д) которых
содержат грань Q. Поскольку грань Q - выпуклая оболочка своих вер-
шин	а любой L-многогранник - выпуклое множество, то для
вершины Д-В v условие принадлежности к системе V(Q) эквивалентно
тому, что L-многогранник £(v) содержит вершины	L-грани Q.
Однако для точки I (г, Я)-системы L принадлежность к числу вершин
L-многогранника £(Д) эквивалентна ее принадлежности к поверхности
описанного вокруг него пустого шара. Таким образом справедливо сле-
дующее утверждение.
Предложение 5.1. 1) Вершина v разбиения Д-В принадлежит к
максимальной маркирующей системе L-грани Q, если и только, если
шар (£(?;)) (с центром v), описанный вокруг соответствующего ей
L-многогранника £(v), содержит все вершины L-грани Q.
2) Для любой L-грани Q ее максимальная маркирующая система
ш = {vjk}p=r есть в точности множество вершин двойственной к ней
грани Д-В.
> Для точки v быть вершиной пустого шара, содержащего на своей
поверхности вершины	грани Q, означает иметь все точки сис-
темы	в качестве ближайших точек (г, Я)-системы L, и значит
102
принадлежать к грани Д-В, двойственной к L-грани Q. Быть при этом
еще и вершиной разбиения Д-В означает принадлежать к числу вершин
этой грани Д-В. •
Это поясняет мотивировку использования термина максимальная
маркирующая система L-грани Q, поскольку это - множество вершин,
на которые будет натянута выпуклая оболочка - область допустимого
перемещения центра пустого шара, опирающегося одновременно на все
вершины L-грани Q.
Таким образом соответствие двойственности, изображенное диа-
граммой на рисунке 5.1, также может быть изображено диаграммой
рисунка 5.2.
L-грань Максимальная	Множество	Грань Д-В
маркирующая система вершин грани Д-В
вершин Д-В
для L-грани
Рис 5.2
Итак, нами установлено взаимно однозначное соответствие (биек-
тивное отображение £ и обратное V)
V{к) <—> L(n — к) к = 0,1,..., п
множества А:-мерных граней разбиения Дирихле-Вороного множеству
(п — &)-мерных граней L-разбиения.
В качестве итога полученных выше результатов, перечислим еще
раз все свойства этого соответствия.
Пусть W — грань разбиения Д-В с вершинами {Г1,... ,Vd} И Q —
двойственная ей грань L-разбиения с вершинами {£,... Тогда:
6)^ = 0™! Ш)-
2.	а) Вершины грани Q — это максимальная образующая систе-
ма L-вершин для грани W, то есть это те точки I (г, Я)-системы L
(или L-вершины), области Д-В V(Z) которых содержат грань W
(ext Q = {li 6 L | V(li) D IT});
б)	Вершины грани W — это максимальная маркирующая система
вершин разбиения Д-В для L-грани Q, то есть это те вершины разбиения
103
Д-В, L-многогранники £[у) которых содержат L-грань Q или, что то
же самое, описанные вокруг них шары (£(£)) содержат все вершины
L-грани Q
3.	Вершины грани Q являются полной системой ближайших точек
множества L для любой относительно внутренней точки грани W, то
есть ext Q = £% (W G ri W).
4.	Грань W есть множество всевозможных центров шаров, не содер-
жащих внутри точек (г, Я)-системы L и содержащих вершины
{fi,... Дт} грани Q на своей поверхности (то есть ’’область движения”
центра пустого подвижного раздувающегося шара, опирающегося на все
вершины {Zi,..., 1т} грани Q).
5.	Грани Q и W лежат в ортогональных дополнительных плоскос-
тях, пересекающихся в единственной точке й — центре А:-мерной сферы,
описанной вокруг вершин грани Q (к = dim Q).
6.	dim W + dim Q = n.
Из первых двух свойств отображений £ и V легко вывести следу-
ющее следствие. Если Qi, Q2 две грани L-разбиения, и W± = V(Qi),
Пд = V(C?2) — соответствующие им грани разбиения Д-В, то выполне-
ние прямого включения Q\ С Q2 L-граней эквивалентно выполнению
обратного включения W± Э W2 граней разбиения Д-В.
Вспомнив определение комбинаторной двойствнности двух
нормальных разбиений пространства на многогранники из §1, можем
сказать, что для данной равномерно-дискретной системы задаваемые
её разбиение Д-В и L-разбиение являются комбинаторно двойственны-
ми. Комбинаторно двойственное соответствие двух разбиений называ-
ют метрически двойственным, если при установлении комбинаторной
двойственности соответствующие друг другу грани этих разбиений рас-
положены в ортогональных дополнительных плоскостях. Как следует из
п.4, разбиение Д-В и L-разбиение являются и метрически двойственны-
ми. Таким образом, имеет место
Теорема 5.2. Для данной ((r,R)-системы разбиение Д-В и L-разби-
ения комбинаторно и метрически двойственны.
> •
104
В заключение приведем рисунок 5.3, на котором изображены двой-
ственные разбиения плоскости на области Дирихле-Вороного и L-много-
гранники (Делоне), заданные некоторой (г, Я)-системой L = {Ц}.
Упражнения
1.	Докажите, что произвольное нормальное разбиение плоскости
на остроугольные треугольники есть L-разбиение. Всегда ли будет
L-разбиением разбиение пространства Е3 на тетраэдры с остроуголь-
ными гранями?
2.	Пусть (г, Я)-система — множество вершин разбиения плоскости
на правильные 6-угольники. Что представляет собой ее разбиение Д-В
и L-разбиение?
3.	Пусть S — множество вершин разбиения Д-В для (г, Я)-системы
L. Является ли множество S равномерно-дискретной системой? При
каких условиях L-разбиение для системы L будет разбиением Д-В для
системы S?
105
Приложение (к главе 3)
Центральная проекция
Пусть П - гиперплоскость в пространстве Еп, у - не содержащаяся в
ней точка, а Щ - гиперплоскость, параллельная П и проходящая через
точку у. Обозначим - открытое полупространство, ограниченное
плоскостью П1 и содержащее плоскость П.
Центральной проекцией с центром Y полупространства на плос-
кость П называется отображение тгу :	> П, ставящее в соответ-
ствие каждой точке X е точку X', полученную пересечением луча
[У, X} с полуплоскостью П (см. рис. 1).
Рис. 1
Если (векторные) координаты точек в пространстве заданы репе-
ром {У; ё1,..., ёп_1, ёп} (с началом в точке У), у которого векторы
ё1,..., ёп_1 параллельны плоскости П, а конец вектора ёп лежит в плос-
кости П (см. рис. 1); то плоскость П задается уравнением хп = 1, а
центральная проекция в координатах задается формулой
Очевидно, что это отображение непрерывно. А потому для любого от-
крытого в гиперплоскости П (п — 1)-мерного множества U его праобраз
7Гу1(?7), т° есть множество открытых лучей (У, X), X G U, проходя-
щих через точки X множества U, — является открытым множеством
(конусом).
106
ЛИТЕРАТУРА
. Бренстед А. Введение в теорию выпуклых многогранников. - М.: Мир,
1988.
. Делоне Б.Н. Геометрия положительных квадратичных форм // Успехи
математических наук. 1937. Вып. III. С. 16-62; 1938. Вып. IV. С.
102-164.
. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы,
оптимизация. - М.: Наука, 1981.
. Ильин В.А., Позняк Э.Г. Линейная алгебра. - М.: Наука, 1974.
. Кострикин А.И. Введение в алгебру. - М.: Наука, 1977.
. Курош А.Г. Курс высшей алгебры. - М.: Наука, 1968.
. Лехтвейс К. Выпуклые множества. - М.: Наука, 1985.
. Постников М.М. Лекции по геометрии. Семестр II. Линейная алгебра. -
М.: Наука, 1986.
. Рыжков С.С., Барыкинский Р.Г., Кучериненко Я.В. Решение основных
задач дискретной геометрии на плоскости. - М.: Изд-во ЦПИ при
механико-математическом факультете МГУ, 2000.
107