Документ взят из кэша поисковой машины. Адрес оригинального документа : http://dfgm.math.msu.su/files/0students/2009-dip-shnurnikov.pdf Дата изменения: Fri May 15 15:44:02 2009 Дата индексирования: Sat Apr 9 22:56:39 2016 Кодировка: Windows-1251 Поисковые слова: р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. Ломоносова

Механико-математический факультет

Дипломная работа

Количества областей в разбиениях плоскости прямыми и другие задачи комбинаторной геометрии.

студента 5 курса кафедры дифференциальной геометрии и приложений И.Н. Шнурникова

Научный руководитель: академик А.Т. Фоменко

Москва 2009


Содержание.
Введение 1. Разбиения плоскости прямыми
1.1 1.2 1.3 1.4 1.5 Примеры, история вопроса и его постановка . . . . . . . . . . . . . . . . . . . Формулировка теоремы и следствия из нее . . . . . . . . . . . . . . . . . . . . Доказательство теоремы и вспомогательных утверждений . . . . Обзор работ предшественников . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Уточнения некоторых доказанных ранее утверждений . . . . . . . . . . . . . 2 4 ........... 4 ........... 5 ........... 6 . . . . . . . . . . 20 . . . . . . . . . . 21 30 30 31

2. Мощность отделяемого множества вершин многомерного куба
2.1 Формулировка и мотивация гипотезы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Доказательства гипотезы в частных случаях . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Серии специальных и ретрагируемых спайнов

41

38 3.1 Оценка количества двумерных клеток специальных спайнов . . . . . . . . . . . . . 38 3.2 Серия специальных спайнов с одной двумерной клеткой. . . . . . . . . . . . . . . . . 40 3.3 Специальные спайны с одной двумерной клеткой аналоги примеров Адамса.

4. Ограничения на топологию 3-многообразий, являющихся пересечением трех квадрик 43
4.1 4.2 4.3 4.4 Возникновение задачи из теории интегрируемых систем . . Условия применимости теорем алгебраической геометрии . Невырожденность в R6 и в С6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Прямая без вещественных точек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 43 44 45 47 49 52 54 56

5. Алгоритмы пересечения поверхностей прямой
5.1 Поверхность вращения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Линейчатая поверхность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Поверхность выдавливания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Литература

1


Введение.
Диплом состоит из пяти независимых друг от друга параграфов, каждый из которых посвящен отдельной задаче комбинаторной геометрии. Первые четыре чисто теоретичны, пятый параграф написан для практического использования.

(1) В параграфе про прямые решен вопрос о том, на сколько областей n прямых делят плоскость. Этот вопрос был впервые поставлен Б. Грюнбаумом в
[Gru72]. Он заметил эквивалентность вопросов для аффинной и вещественной проективной плоскостей. Н. Мартинов в [M ar93] в качестве ответа привел некоторое подмножество множества натуральных чисел, показал, что каждое число из этого подмножества подходит, и попытался доказать, что числа не из этого подмножества не подходят. Не зная об этих работах, В.И. Арнольд в [Арн08] поставил еще раз вопрос о количестве областей и доказал неравенства, из которых можно сформулировать ответ. Мною доказано, что числа не из множества Н. Мартинова не подходят, т.е. вопрос Б. Грюнбаума теперь решен полностью. В ходе приведенного ниже доказательства (теоремы 1, впервые сформулированной Н. Мартиновым) были усилены неравенства В.И. Арнольда.

А.Немировского, К.Роса утверждает, что любая касательная гиперплоскость к сфере строго отделяет от центра сферы не более чем 2n-2 вершин куба. В разделе 2.2 доказана эта гипотеза для n 6 (теорема 2). Построена серия примеров гиперплоскостей, строго отделяющих ровно 2n-2 вершин n-мерного куба для любого n (пример 2). Доказано, что гиперплоскости, ортогональные радиус-векторам вершин куба, строго отделяют менее чем 2n-2 вершин куба при n 3 (теорема 3).

(2) Рассмотрим n-мерный куб и вписанную в него сферу. Гипотеза А.Бен-Тала,

(3) В параграфе про спайны оценено количество специальных ретрагируемых спайнов. (а) Оценка количества двумерных клеток специальных спайнов. (б) Улучшенная оценка количества незамкнутых гиперболических многообразий из [F M P 03] (лемма 2). Оценка осталась экспоненциальной, однако увеличилось основание с 6 до 6 2. Для этого был рассмотрен новый граф особенностей и подходящий для него способ подсчета спайнов. (в) По идее А. Т. Фоменко регулярные окрестности особых графов в спайнах многообразий из [F M P 03] были проверены на возможность ретрагироваться на свою границу (границу окрестности) и доказано, что все они ретрагируются (лемма 3). Т.е. как следствие существует много двумерных полиэдров, обобщающих примеры Адамса. (4) В параграфе про квадрики найдены:
Q3 = {f1 (z1 , . . . , z6 ) = d1 , C
(а) условия на параметры квадрик, при которых совместная поверхность уровня

f2 (z1 , . . . , z6 ) = d2 ,

f3 (z1 , . . . , z6 ) = d3 }

невырождена в C6 (теорема 4 и замечание к ней), (б) явно найдена прямая (лежащая в Q3 C6 ), определяемая вещественным паC раметром и комплексным (для почти всех исходных многообразий Q3 ) параметром R ч, на которой нет точек с вещественными координатами. 2


Найденную прямую можно использовать для применения теоремы Коллара (см. [K ol]) для определения топологического типа трехмерного многообразия, заданного в R6 тремя квадратичными уравнениями (интегралом площадей f2 , геометрическим интегралом f1 и гамильтонианом f3 движения четырехмерного твердого тела): 1. x2 + x2 + x2 + x2 + x2 + x2 = d1 , 1 2 3 4 5 6 2. x1 x4 + x2 x5 + x3 x6 = d2 , 3. c1 x2 + c2 x2 + c3 x2 + c4 x2 + c5 x2 + c6 x2 = d3 . 1 2 3 4 5 6 Для трех поверхностей компьютерной геометрии поверхности вращения, линейчатой поверхности и поверхности выдавливания приведены явные алгоритмы, находящие все точки пересечения поверхности и прямой. Поверхности заданы в параметрическом виде, и система двух уравнений двух неизвестных (определяющая точки пересечения) сведена к одному уравнению одного неизвестного.

(5) Алгоритмы пересечения поверхностей прямой.

3


1. Разбиения плоскости прямыми.
Рассмотрим набор , состоящий из n попарно различных проективных прямых на вещественной двумерной проективной плоскости RP2 . Удалим из плоскости RP2 (с обычной топологией) все точки всех прямых набора , получим подмножество плоскости RP2 . Наделим полученное подмножество индуцированной (из плоскости RP2 ) топологией. Если получившееся топологическое пространство имеет ровно f компонент связности, то будем говорить, что набор прямых делит плоскость RP2 на f областей. Цель раздела 1. состоит в нахождении (для каждого натурального числа n) значений f (количеств областей) для плоскости RP2 , разделенной всеми возможными наборами прямых . Гипотетическая формула для возможных значений количеств областей, примеры наборов прямых, разделяющих плоскость RP2 на любое задаваемое формулой число, были известны с 1993 года, см. [M ar93], см. утверждения 3 и 4 пункта 1.3. В пункте 1.3 доказано, любое число, не задаваемое формулой (для возможных значений количеств областей), не может быть количеством областей разделенной плоскости RP2 (теорема 1). Таким образом, теперь известны все возможные количества областей и доказано, что другие числа не возможны.

состоящим из n прямых, назовем nнедостижимыми. Пример 1. Одна прямая делит плоскость RP2 на одну область; две прямые делят на две области; три прямые делят на три или на четыре области; четыре прямые делят на 4, 6 или 7 областей. Пример 2. Если все прямые набора пересекаются в одной точке, то число областей равно n числу прямых набора. Пример 3. Если все прямые набора, кроме одной, пересекаются в одной точке, то число областей равно 2(n - 1). Пример 4. Если все прямые набора, кроме двух, пересекаются в одной точке, то число областей равно 3(n - 2) или 3n - 5. Пример 5. Если все прямые набора, кроме трех, пересекаются в одной точке, то число областей равно 4(n - 3), или 4n - 11, или 4n - 10, или 4n - 9. Пример 6. Если все прямые набора, кроме i < n , пересекаются в одной точке, 2 то число областей равно (i + 1)(n - i) + j, где число j это любое целое число из отрезка [0, i(i-1) ]. 2 Пример 7. Если среди прямых набора ровно n - k проходят через одну точку, то число областей не менее (k + 1)(n - k ). Б. Грюнбаум в [Gru72] доказал n-недостижимость всех натуральных чисел из отрезков

1.1 Примеры, история вопроса и его постановка. Определение. Те натуральные числа из отрезка [n, 1 + n(n2-1) ], которые не могут быть количеством областей проективной плоскости RP2 , разделенной набором ,

[n + 1, 2n - 3] при n

4

и

[2n - 1, 3n - 7] при n 9.

6

и выдвинул гипотезу (2.4) о n-недостижимости всех чисел из отрезка

[3n - 4, 4n - 13] при n
4


Эту гипотезу решили Н.Д. Мартинов в [M ar90], а также Р. Кордовил в 1980 году и Г.И. Пурди в 1980 году. Позже Н.Д. Мартинов в [M ar93] сформулировал теорему, определяющую все n недостижимых чисел (и доказал ее в одну сторону). Привел примеры наборов прямых, делящих плоскость на любое число, заявленное им как nдостижимое. Опубликовал неверное доказательство того, что все заявленные им nнедостижимые числа действительно nнедостижимы. Итак, мне оставалось доказать nнедостижимость чисел (заявленных как недостижимые) (см. теорему 1). Однако я не знал работ Н.Мартинова и Б.Грюнбаума, поэтому я переоткрыл теорему Мартинова и дал другое доказательсво достижимости (см. утверждения 3 и 4).

1.2 Формулировки теорем и следствия из них. Обозначение. Для набора прямых за n() обозначим количество прямых в нем, а за f () обозначим количество областей разделенной им плоскости RP2 . Утверждение 1. Для всех наборов прямых верны неравенства
n() f () 1+ n()(n() - 1) 2

Индукция по числу n() прямых в наборе. База n() = 1 тогда f () = 1. Переход: вырезание nй прямой (при n 2) увеличивает число областей настолько, сколько точек пересечения nя прямая имела с предыдущими n - 1й, т.е. от 1 до n - 1.

Обозначение. Для каждого натурального n 4 за dn обозначим число 2n - 5 3 - 4 Замечание про число dn . Для всех натуральных чисел n 4 верны неравенства
d2 + 3dn n +3 2 n d2 + dn n +3 2

1 2

По определению целой части получаем

dn
Прибавляя ко всем трем частям
1 2

31 2n - 5 - < dn + 1 42
и возводя все в квадрат, имеем

d2 + dn + n

1 4

9 3 2n - 5 < d2 + 3dn + n 4 4

3 Прибавим ко всем трем частям 5 4 и заметим четность d2 + 3dn . n Обозначение. Для всех натуральных чисел n k 2 за f (n, k ) обозначим минимально возможное количество областей плоскости RP2 , разделенной n прямыми с максимальной кратностью точек пересечения ровно k , (т.е. есть точка пересечения k прямых и нет точек пересечения хотя бы k + 1 прямых).

5


Утверждение 7. Для натуральных чисел k
f (n, k ) 2

2иn

k + 1 верно неравенство (1)

n2 - n + 2k k+3

Теорема 1. (а) Для всех наборов прямых c n = n() верно включение
dn -1

f ()
k=0

[(k + 1)(n - k ); (k + 1)(n - k ) +

k (k - 1) ] 2

[(dn + 1)(n - dn ); 1 +

n(n - 1) ] () 2

где dn = [ 2n - 5 3 - 1 ] при n 3 и d1 = d2 = 0. 4 2 (б) Все натуральные числа множества
dn -1

[(k + 1)(n - k ); (k + 1)(n - k ) +
k=0

k (k - 1) ] 2

[(dn + 1)(n - dn ); 1 +

n(n - 1) ] 2

()

являются n-достижимыми. Замечание. Множество делено корректно (т.е. знак натурального ряда), так как хотя бы для одного i. Знак левых границ i + 1-х хотя бы

достижимых чисел, приведенное в теореме 1, опрестоит между непересекающимися отрезками чисел при n 4 верно dn 1 и dn - 1 i 0 выполняется стоит, потому что правые границы i-х отрезков меньше на два, то есть

(i + 1)(n - i) +

i(i - 1) 2

(i + 2)(n - i - 1) - 2 dn - 1 и поэтому i2 + 3i +4 2 d2 + dn n +3 2

i(i - 1) +i+2 2

n - i - 2,

(0)

что выполняется, так как i

n

по замечанию про число dn . Замечание. Множество достижимых чисел, приведенное в теореме 1, состоит из dn + 1 подмножеств подряд идущих натуральных чисел, причем из неравенства (0) предыдущего замечания следует, что между каждыми двумя соседними подмножествами есть хотя бы одно n-недостижимое число. Замечание. Рассмотрим n кривых на проективной плоскости RP2 , каждая из которых делит проективную плоскость RP2 на одну область, и кривые попарно пересекаются в одной точке. Такие кривые называются в [GP W 05] псевдопрямыми. Теорема 1 для таких кривых верна, а ее доказательство аналогично.

1.3 Доказательства теоремы и вспомогательных утверждений. Обозначение. Для произвольного набора n различных прямых на проективной плоскости RP2 за aj обозначим число точек пересечения кратности ровно j.
не более k

Утверждение 2. Пусть в наборе из n
k

2 прямых в одной точке пересекаются n. Тогда этот набор делит плоскость RP2 на 1+
j =2

aj (j - 1) областей.
6


Индукция по n, база n = 2, тогда k = 2, a2 = 1 и две прямые делят плоскость RP на две области. Предположим, что утверждение 2 верно для любого набора из n - 1 прямой. Удалим из (остатка) плоскости RP2 ещ? одну (произвольную) прямую ln . Если прямая ln пересекает объединение первых n - 1 прямых в p > 0 точках, то удаление прямой ln приведет к разделению p частей остатка плоскости RP2 на две каждая, величина 1 + k=2 aj (j - 1) увеличится на p (при переходе n - 1 n числа aj j и k могут измениться). Число областей и значение формулы при переходе индукции увеличились на равные числа p и, следовательно, остались равными.
2

ства

Утверждение 3. Для всех натуральных n

4 все натуральные числа множе-

n 2

[(k + 1)(n - k ); (k + 1)(n - k ) +
k=0

k (k - 1) ] 2

являются

n - достижимыми.

k(k-1) n Для всех целых чисел 0 k и0 t покажем существование n 2 2 2 прямых l1 , . . . , ln , делящих плоскость RP на (k + 1)(n - k ) + t областей. Представим t в виде

t = (k - 1) + (k - 2) + ћ ћ ћ + (k - q ) + rq ,
где 0 rq k - q - 1 и 0 q k - 1 (выберем любое представление). Возьмем k - q - 1 прямых l1 , l2 , . . . , lk-q-1 пересекающимися в точке A, прямая lk-l пересекает их в точках A1 , A2 , . . . , Ak-q-1 (отличных от точки A). Прямые lk-q+1 , . . . , lk-q+n-k пересекаются в точке O, причем прямая lk-q+i проходит через точку Ai для 1 i k - q - 1 - rq . Прямая lk-q+k-q-rq проходит через точку A. Возможность следует из неравенства n - k > k - q - rq . Точки O, A, A1 , . . . , Ak-q-1 попарно различны и каждая из них (назовем е? X ) принадлежит только тем прямым, которые описаны выше как проходящие через точку X. Все остальные точки пересечения n прямых друг с другом имеют кратность 2 (т.е. каждая из прямых ln-q+1 , . . . , ln не проходит через точки пересечения других прямых). Для нахождения числа областей плоскости RP2 применим утверждение 2, для этого сначала посчитаем сумму кратностей, уменьшенных на 1, для групп точек пересечения:

ћ rq для точек Ak

-q -rq

,...,A

k-q -1

,

ћ n - k - 1 для точки O, ћ (n-k )(k -q ) для точек пересечения прямых l1 , . . . , l
k -q

с прямыми l

k-q +1

,...,l

n- q

,

ћ ((n - q ) + (n - q + 1) + ћ ћ ћ + (n - 1)) для точек пересечения прямых l1 , . . . , l с прямой ln-q+i+1 для всех i = 0, 1, . . . , q - 1.

n-q +i

А затем сложим полученные числа вместе и вместе с единицей, получим равенство числа областей плоскости RP2 сумме

1 + rq + (n - k - 1) + (n - k )(k - q ) + ((n - q ) + (n - q + 1) + ћ ћ ћ + (n - 1)) =
7


= rq + (n - k )(k - q + 1) + (n - q )q + = (n - k )(k + 1) + (k - q )q + rq +
Тем самым доказательство завершено.

q (q - 1) = 2

q (q - 1) = (n - k )(k + 1) + t. 2 4 все натуральные числа множе-

ства [(dn + 1)(n - dn ); 1 + n(n2-1) ] являются n-достижимыми. Все натуральные числа множества

Утверждение 4. Для всех натуральных n

[(dn + 1)(n - dn ); (dn + 2)(n - dn - 1) - 1] [(dn + 1)(n - dn ); (dn + 1)(n - dn ) +
2

dn (dn - 1) ] 2

dn -dn по замеявляются n-достижимыми по утверждению 3 и т.к. n - 2dn - 3 2 чанию про число dn . Значит, осталось доказать n-достижимость натуральных чисел множества

[(dn + 2)(n - dn - 1); 1 +

n(n - 1) ]. 2

Так как

(dn + 2)(n - dn - 1) + n2 -n 2

dn (dn + 1) (n - dn - 2)(n - dn - 3) + = 2 2

=

2dn + 5 n2 - n - (dn + 2) + 1 = 1 + , 2 2 то

1+

n2 - n = (dn + 2)(n - dn - 1) + ((n - dn - 3) + ћ ћ ћ + 1) + ((dn ) + ћ ћ ћ + 1) 2

любое натуральное число m, такое, что

(dn + 2)(n - dn - 1)

m

1+

n(n - 1) 2

можно представить хотя бы одним способом в виде

m = (dn + 2)(n - dn - 1) + ((n - dn - 3) + ћ ћ ћ + (n - dn - a)) + (dn + ћ ћ ћ + (dn - p)) + rp ,

где 2

a

(n - dn - 1),

-1

p

(dn - 1) и 0

rp

(dn - p - 1),

(причем a = 2 означает отсутствие суммирования первой группы слагаемых), т.к.

(dn + 2)(n - dn - 1) + (n-dn -2)(n-dn -3) , то берем a = n - dn - 2 1, p = max{q -1|m - (dn + 2)(n - dn - 1) - (n-dn -2)(n-dn -3) - (dn + ћ ћ ћ + (dn - q )) 2 (n-dn -2)(n-dn -3) 0}, а rp = m - (dn + 2)(n - dn - 1) - - (dn + ћ ћ ћ + (dn - p)) ; 2
8

вариант 1): если m


, то берем a = max{b 2|m - (dn + 2)(n - dn - 1) - (n - dn - 3) - ћ ћ ћ - (n - dn - b) 0}, вариант 2)а): если m - (dn + 2)(n - dn - 1) - ((n - dn - 3) - ћ ћ ћ - (n - dn - a)) > 0, то p = max{q -1|m - (dn + 2)(n - dn - 1) - (n - dn - 3) - ћ ћ ћ - (n - dn - a) - (dn + ћ ћ ћ + (dn - q )) 0}, а rp = m-(dn +2)(n-dn -1)-((n - dn - 3) - ћ ћ ћ - (n - dn - a))- (dn + ћ ћ ћ + (dn - q )) ; вариант 2)б): если m - (dn + 2)(n - dn - 1) - ((n - dn - 3) - ћ ћ ћ - (n - dn - a)) = 0, то p = -1, r-1 = 0. 2 n Так как n - dn - 4 dn + (dn - 1) + ћ ћ ћ + 1 = dn (d2 +1) следует из n 4 + dn +3dn , 2 то p в варианте 2)а) найдется всегда. Теперь построим набор n прямых, делящих плоскость RP2 на m (с прежними ограничениями) областей: Пусть dn - p - 1 прямых l1 , . . . , ldn -p-1 пересекаются в точке A, прямая dn - p пересекает их в точках A1 , . . . , Adn -p-1 . Выберем точку O вне прямых l1 , . . . , ldn -p . Прямые ld
n

вариант 2): если m < (dn + 2)(n - dn - 1) +

(n-dn -2)(n-dn -3) 2

-p-1

,...,l

dn -p+(n-dn -1)-(a-2)

пересекаются в точке O, прямые

ld

n

-p+(n-dn -1)-(a-2)+1

,...,l

dn -p+(n-dn -1)

не проходят через точку O и любые три прямые из прямых

ld

n

-p+1

,...,l

dn -p+(n-dn -1)

или не пересекаются в одной точке, или пересекаются в точке O. Также прямая ldn -p+i+1 проходит через точку Ai для каждого

i = 1, . . . , dn - p - 1 - rp .
Прямая ldn -p+1 проходит через точку A. Возможность гарантируется первым неравенством из следующих:

(dn - p) + 1 + (dn - p - 1 - rp ) n 2dn + 2

(dn - p) + (n - dn - 1)

d2 + dn n + 3 2dn + 2 (dn - 1)(dn - 2) 0. 2 Через точки O, A, A1 , . . . , Adn -p-1 проходят только те прямые, про которые их прохождение написано, все остальные точки пересечения имеют кратность 2. Возможность следует из того, что прямые, проходящие через точку A : l1 , . . . , l
dn -p-1

и

ld

n

-p+1

;

и прямые, проходящие через (точку O и хотя бы одну из точек Ai ,) вне точек O, A по хотя бы три не пересекаются, все их точки пересечения с прямой ldn -p это точки Ai , а остальные прямые проходят через не более чем одну из точек O, Ai (через точку A никакая оставшаяся прямая не проходит). Для нахождения числа областей плоскости RP2 применим утверждение 2, для этого сначала посчитаем сумму кратностей, уменьшенных на 1, для групп точек пересечения: 9


ћ (n - dn - 1) - a + 1 для точки O, ћ (dn + 1)(n - dn - 1) для точек пересечения прямых l1 , . . . , l остальных,
dn -p

,l

n- p

, . . . , dn и

ћ ((n - dn - 1 - a + 2) + ћ ћ ћ + (n - dn - 1 - a + a - 1)) для точек пересечения прямых ldn -p+1 , . . . , ldn -p+n-dn -1 , отличных от точки O, ћ ((dn - p) + ћ ћ ћ + dn ) для точек пересечения прямых l1 , . . . , l личных от точек A, A1 , . . . , Adn -p , ћ rp для точек Ad
n

dn -p

,l

n- p

, . . . , dn , от-

-p-rp

...,A

dn -p-1

.

А затем сложим полученные числа вместе и вместе с единицей, получим, что число областей плоскости RP2 равно сумме

1+((n-dn -1)-a+1)+(dn +1)(n-dn -1)+((n - dn - 1 - a + 2) + ћ ћ ћ + (n - dn - 1 - a + a - 1)) + + ((dn - p) + ћ ћ ћ + dn ) + rp = = rp +(dn + ћ ћ ћ + (dn - p))+((n - dn - a) + ћ ћ ћ + (n - dn - 3))+(dn +2)(n-dn -1) = m.
Тем самым доказательство завершено.

Пример. Перечислим крайние случаи доказательства утверждения 4:
ћ если dn - 1 = p, то точек A, Ai нет, ћ если a = 2, то в точке O пересекаются n - dn - 1 прямая, ћ если a = n - dn - 1, то в точке O пересекаются две прямые, ћ если p = -1, то dn + 1 прямая пересекаются в точке A, ћ если p = dn - 2, то точки A нет, а точка A1 есть, ћ если rp = 0, то через каждую из точек A1 , . . . , A
dn -p-1

проходит по три прямые,
dn -p-1

ћ если rp = dn - p - 1, то через каждую из точек A1 , . . . , A прямые.

проходит по две

Утверждение 5. Пусть существуют такие натуральные числа m, n, k, что число m является n-достижимым и
(k + 1)(n - k ) > m > k (n - k + 1) + (k - 1)(k - 2) . 2

Тогда в любом наборе из n прямых, разбивающих плоскость RP2 на m областей, кратность любой точки пересечения не превосходит k . Предположим противное: существует набор с точкой пересечения A кратности q k + 1. Для оценки числа областей плоскости RP2 применим утверждение 2, для этого сначала посчитаем сумму кратностей, уменьшенных на 1, для групп точек пересечения: 10


ћ q - 1 для точки A, ћ q (n - q ) для точек пересечения q прямых, проходящих через точку A, с остальными n - q прямыми.
А затем сложим полученные числа вместе и вместе с единицей, получим, что

m

1 + (q - 1) + q (n - q ) = q (n - q + 1).

Разберем два случая. (а) Если q n - k , то из k + 1

q

n - k следует
противоречие.

m

q (n - q + 1)

(k + 1)(n - k ) > m,

(б) Если q n - k + 1, то для оценки числа областей плоскости RP2 применим утверждение 2, для этого сначала посчитаем сумму кратностей, уменьшенных на 1, для групп точек пересечения:

ћ q - 1 для точки A, ћ q (n - q ) для точек пересечения q прямых, проходящих через точку A, с остальными n - q прямыми. ћ
(n-q )(n-q -1) 2

для точек пересечения n - q прямых друг с другом.

А затем сложим полученные числа вместе и вместе с единицей, получим, что

m

1 + (q - 1) + q (n - q ) +

(n - q )(n - q - 1) (n - q )(n - q - 1) = q (n - q + 1) + . 2 2 (k + 1)(n - k ) > m > k (n - k + 1) (k + 1)(n - k ) > k (n - k + 1) + 1, 2k + 2, поэтому n + 2, 2 (k - 1)(k - 2) , 2

Из неравенства следует

сократив на k (n - k ), получим n - k > k + 1 и n

l
значит

n-k+1

l(n - l + 1)
поэтому m

(n - k + 1)k
(k-1)(k-2) 2

и

(n - l)(n - l - 1) 2

k (n - k + 1) +

. Противоречие. k 2 верно неравенство

Утверждение 6. Для всех натуральных чисел n
f (n, k ) 1+

n(n - 1) . k Для любого набора из n прямых, из которых не более k пересекаются в одной точке, делящего плоскость RP2 на f (n, k ) областей и имеющего aj точек пересечения кратности i, верно неравенство
11


f (n, k )

1+

n(n - 1) k - 2 + (a2 + ћ ћ ћ + ak-1 ). k k

Рассмотрим любой набор из n прямых, из которых не более k пересекаются в одной точке, и набор прямых делит плоскость RP2 на f (n, k ) областей. По утверждению 2
k

f (n, k ) = 1 +
i=2

(i - 1)ai .

Число пар прямых равно

n(n - 1) = 2

k

a
i=2

i

i(i - 1) , 2

так как на плоскости RP2 любые две прямые пересекаются и точка пересечения 2 кратности i дает i(i-1) пару прямых. Умножим равенство числа пар на k и выделим 2 выделим сумму из равенства утверждения 2, получим

n(n - 1) = k

k

i=2

i(i - 1) ai = k

k

k

ai (i - 1) -
i=2 i=2

a

i

i-1-

i(i - 1) k

.

Заметим, что множители в последней сумме равны

i-1-

i(i - 1) k

=

(i - 1)(k - i) k
k

k-2 k

при

2

i

k - 1.

Поэтому и

n(n - 1) k 1+

ai (i - 1) -
i=2

k-2 (a2 + ћ ћ ћ + ak-1 ) k
k-1

f (n, k )

n(n - 1) k - 2 + (a2 + ћ ћ ћ + a k k 2иn

)

Утверждение 7. Для натуральных чисел k
f (n, k ) 2

k + 1 верно неравенство (1)

n2 - n + 2k k+3

Рассмотрим любой набор из n прямых, из которых не более k пересекаются в одной точке, делящий плоскость RP2 на f (n, k ) областей. За aj (как и раньше) обозначим число точек пересечения кратности j. Докажем неравенство Е. Мельхиора из [M el41] : a2 3 + a4 + 2a5 + ћ ћ ћ + (k - 3)ak (2) Так как n k + 1, то на каждой прямой есть хотя бы две точки пересечения с другими прямыми. Поэтому каждая область проективной плоскости ограничивается хотя бы тремя отрезками прямых. Обозначим за bj число областей, ограниченных ровно j отрезками, j = 3, 4, . . . , x. По утверждению 2 число областей проективной плоскости равно

f (n, k ) = b3 + ћ ћ ћ + bx = 1 + a2 + ћ ћ ћ + (k - 1)ak
12

(3)


Для каждой области посчитаем число отрезков прямых, ее ограничивающих и сложим эти числа для всех областей, получим 3b3 + 4b4 + ћ ћ ћ + xbx . С другой стороны, каждый отрезок (между двумя соседними точками пересечения) каждой прямой посчитается два раза (для двух областей, к нему примыкающих). На каждой прямой отрезков столько же, сколько и точек пересечения. Сумма по всем прямым количества точек пересечения, находящихся на прямой (суммируемой) равна сумме кратностей всех точек пересечения, то есть равна

2a2 + 3a3 + ћ ћ ћ + k ak .
Приравняв посчитанное двумя способами, получим

3b3 + 4b4 + ћ ћ ћ + xbx = 2(2a2 + 3a3 + ћ ћ ћ + k ak )
Вычитая из равенства (4) правое равенство (3), умноженное на 3, получим

(4)

b4 + 2b5 + ћ ћ ћ + (x - 3)bx = -3 + a2 - a4 - ћ ћ ћ - (k - 3)a

k

(5)

Неравенство (2) следует из неотрицательности левой части равенства (5). Перепишем неравенство (2) в виде

-a2 + a4 + 2a5 + ћ ћ ћ + (k - 3)ak

-3

(6)

По утверждению 2 для рассматриваемого набора прямых верно равенство:

a2 + 2a3 + ћ ћ ћ + (k - 1)ak = f (n, k ) - 1
Умножим неравенство (6) на венство
k k -1 2

(7)

, а равенство (7) на

k+3 2

и сложим, получим нера-

ai
i=2

k-1 k+3 (i - 3) + (i - 1) 2 2

-3

k-1 2

+ (f (n, k ) - 1)

k+3 2

(8)

Для упрощения и оценки левой части неравенства (8) заметим

k-1 k+3 (i - 3) + (i - 1) = ik + i - 2k 2 2

i(i - 1)

(9) 0, которое

так как правое неравенство (9) равносильно неравенству (i - 2)(i - k ) верно при используемых значениях индекса суммирования 2 i k . Удвоенное число пар прямых равно

2a2 + 6a3 + ћ ћ ћ + k (k - 1)ak = n(n - 1)

(10)

Из неравенства (9), примененного к левым частям неравенства (8) и равенства (10) следует неравенство правых частей (8) и (10):

-3

k-1 2

+ (f (n, k ) - 1)

k+3 2

n(n - 1)

(11)

Откуда и следует требуемое неравенство

f (n, k )

2

n2 - n + 2k k+3
13

(1)


ния 7 обращается в равенство при условии b4 = b5 = ћ ћ ћ = bx области треугольные. Это возможно, например, в следующих 1) k 2, n = k + 1, тогда a2 = k , a3 = ћ ћ ћ = ak-1 = 0, ak = 1, 2) k = 4, n = 13, a2 = 12, a3 = 4, a4 = 9, см. рис. (n = 13). 3) k = 3, n = 6, a2 = 3, a3 = 4, см. рис. (n = 6). 4) k = 3, n = 7, a2 = 3, a3 = 6 см. рис. (n = 7). В случаях 1), 3), 4) оценка (1) утверждения 7 точна. Требование n k + 1 необходимо, так как используется в f (n = k , k ) = k оценка (1) неверна.

Замечание к утверждению 7. Неравенство (2) из доказательства утвержде-

= 0, то есть когда все случаях: см. рис. (n = k + 1).

доказательстве, и для

Утверждение 8. Выберем натуральные числа a 2иb 1. На евкли2 довой плоскости R рассмотрим попарно параллельные прямые l1 , . . . , la . Прямые

la+1 , la+2 , . . . , l2a попарно параллельны и перпендикулярны прямым l1 , . . . , la . Прямые k l2a+1 , . . . , l2a+b не паралелльны прямым l1 , . . . , la , la+1 , . . . , l2a . За s = j =2 aj (j - 1) обозначим сумму уменьшенных на 1 кратностей точек пересечения (находящихся на евклидовой плоскости) всех 2a + b прямых между собой, где aj это количество точек пересечения кратности j (как и раньше). Тогда верно неравенство s 4ab + 2a2 + 2a - 3 3 (1)

Перенумеруем (если надо) прямые l1 , . . . , la и (отдельно) прямые la+1 , la+2 , . . . , l2a по порядку их расположения на плоскости. Для каждого 1 i, j a точкой Aij назовем точку пересечения прямых li и la+j . Для каждой прямой l2a+m , где 1 m b, за tm обозначим количество лежащих на ней точек Aij . Количество точек пересечения прямой l2a+m с прямыми l1 , . . . , l2a , отличных от точек Aij , равно 2a - 2tm . Если прямая l2a+m не проходит через пару точек A1b , Aa1 или пару точек A11 , Aab , то количество пар лежащих на прямой l2a+m различных точек Aij , между которыми нет точек пересечения прямой l2a+m с прямыми l1 , . . . , l2a , не менее (tm - 1) - (2a - 2tm - 1). Если прямая l2a+m проходит через одну из двух указанных пар точек, то количество пар не менее (tm - 1) - (2a - 2tm ). Обозначим сумму про всем прямым l2a+1 , . . . , l2a+b этих количеств пар за T . С другой стороны, любая пара точек Aij без точек прямых l1 , . . . , l2a между ними есть диагональ какого-то из (a - 1)2 прямоугольников Aij A(i+1)j A(i+1)(j +1) Ai(j +1) для 1 i, j a - 1. Каждая пара точек принадлежит не более, чем одной из прямых l2a+1 , . . . , l2a+b , поэтому, складывая оценки количеств по всем прямым l2a+1 , . . . , l2a+b , получим неравенство:
b

2(a - 1)

2

T

-2 +
m=1

(3tm - (2a))

(2)

Рассмотрим отдельно два случая. (а) Верно неравенство T > (a - 1)2 . По принципу Дирихле хотя бы в T - (a - 2 1) прямоугольниках Aij A(i+1)j A(i+1)(j +1) Ai(j +1) обе диагонали являются отрезками каких-то из прямых l2a+1 , . . . , l2a+b . Оценим сумму s, посчитав

ћ пересечения прямых l1 , . . . , la с прямыми la+1 , . . . , l
14

2a

как a2 ,


ћ пересечения прямых l

2a+1

,...,l

2a+b

с прямыми l1 , . . . , l

2a

как

b m=1

(2a - tm ),

ћ пересечения диагоналей прямоугольников как T - (a - 1)2 .
Сложим посчитанные пересечения в неравенство
b

s

a2 +

(2a - tm ) + T - (a - 1)2
m=1

(3)

Умножим неравенство (3) на 3 и сложим с правым неравенством (2), получим неравенство 3s 4ab + 2T - 3(a - 1)2 + 3a2 - 2 (4) Заменяя в неравенстве (4) T по имеющемуся в случае (а) неравенству T и деля обе части (4) на 3, получим

(a - 1)2 + 1,

s
(б) Верно неравенство T прямоугольников, оценим

4ab + 2a2 + 2a - 1 3

(5)

(a - 1)2 . Аналогично случаю (а), только без диагоналей
b

s

a2 +

(2a - tm )
m=1

(6)

Умножим оценку (6) на 3 и сложим с неравенством (2), получим

3s

4ab + 3a2 - 2 - T

(7) (a - 1)2 , и

Заменяя в неравенстве (7) T по данному в случае (б) неравенству T деля обе части (7) на 3, получим

s

4ab + 2a2 + 2a - 3 3

(8)

Оба случая (а), (б) дали оценки (5), (8), достаточные для неравенства (1).
+ 5, n k 2 k + 3 рассматриваются все наборы из n прямых на проективной плоскости RP2 , в которых не более k прямых пересекаются в одной точке и есть хотя бы две точки пересечения ровно k прямых. Прямые каждого рассматриваемого набора делят плоскость RP2 хотя бы на (k + 1)(n - k ) областей. Возьмем любой рассматриваемый набор прямых. Обозначим число областей плоскости RP2 , разделенной прямыми рассматриваемого набора, за f . Выберем любые две различные точки пересечения k прямых (каждая) и обозначим их за A и B . Возможны только два случая: Случай (а). Каждая из прямых рассматриваемого набора не содержит одновременно точек A и B . Выделим в проективной плоскости RP2 евклидову плоскость R2 так, что обе точки A и B оказались бы на бесконечности, а прямые, проходящие через

Утверждение 9. Для всех натуральных чисел k

2

15


точку A, перпендикулярны прямым, проходящим через точку B . Применим утверждение 8 с a = k , b = n - 2k . Прямые, проходящие через точку A, будут прямыми l1 , . . . , la , проходящие через точку B прямыми la+1 , . . . , l2a , остальные прямые набора будут прямыми l2a+1 , . . . , l2a+b . Возможность применения утверждения 8, то есть неравенства

k2 + k + 3 - 2k 1 2 следуют из условия k 5. Для оценки f , помимо оценки на сумму s из утверждения 8, добавим вклад точек A, B и единицу, то есть f s + (k - 1) + (k - 1) + 1 и получим оценку 4k n - 6k 2 + 8k - 6 f (1) 3 Осталось (в случае (а)) доказать неравенство для правой части (1): a=k 2, b = n - 2k 4k n - 6k 2 + 8k - 6 3 (k + 1)(n - k ) (2)

В неравенстве (2) перенесем слагаемые с n в большую, а без n в меньшую части неравенства, приведем подобные слагаемые и домножим обе части на 3, получим

(k - 3)n
Заметим, что

3k 2 - 11k + 6

(3)

3k 2 - 11k + 6 = (k - 3)(3k - 2) и k - 3 > 0,
поэтому неравенство (3) можно сократить на k - 3 и получить n следует из

3k - 2, что

k2 + k k2 + k +3 и + 3 3k - 2 k 2 - 5k + 10 0. 2 2 Случай (а) разобран. Случай (б). Одна из n прямых (назовем е? ln ) проходит через обе точки A, B . Выделим в проективной плоскости RP2 евклидову плоскость R2 = RP2 \ln так, что k - 1 прямых, проходящих через точку A, перпендикулярны k - 1 прямым, проходящим через точку B . Применим утверждение 8 с a = k - 1, b = n - 2k + 1 к прямым l1 , . . . , la , la+1 , . . . , l2a , проходящим через точки A, B и к остальным прямым l2a+1 , . . . , l2a+b , удаленную на бесконечность прямую ln не используем. Возможность применения утверждения 8, то есть неравенства n k2 + k + 3 - 2k 1 2 следуют из условия k 5. Для оценки f , помимо оценки на сумму s из утверждения 8, добавим вклад точек пересечения прямой ln с остальными прямыми и единицу, получим n(4k - 1) - 6k 2 + 10k - 7 (4) f 3 a=k-1 2, b = n - 2k + 1
16


Осталось (в случае (б)) доказать неравенство для правой части (4):

n(4k - 1) - 6k 2 + 10k - 7 3

(k + 1)(n - k )

(5)

В неравенстве (5) перенесем слагаемые с n в большую, а без n в меньшую части неравенства, приведем подобные слагаемые и домножим обе части на 3, получим

(k - 4)n
По условию n
k +k 2
2

3k 2 - 13k + 7

(6)

+ 3. Неравенства

k2 + k + 3 > 3k + 2 k 2 - 5k + 2 > 0 и 2 (k - 4)(3k + 2) = 3k 2 - 10k - 8
верны при k

3k 2 - 13k + 7

5. (k - 4)n > (k - 4)(3k + 2) 3k 2 - 13k + 7,

Поэтому

что доказывает (6) и завершает случай (б). В обоих случаях (а), (б) доказано f (k + 1)(n - k ).

Утверждение 10. Для всех натуральных чисел
k 2, l 2 k + 1, n l2 + l +2 2
верно неравенство

n2 - n + 2k k+3
k+3 2

(l + 1)(n - l + 1)

(1)

Домножим неравенство (1) на

и сгруппируем слагаемые по степеням n :

n2 - n

2 + (l + 1)(k + 3) 2

+

4k + (l2 - 1)(k + 3) 2

0

(2)

Выделим полный квадрат относительно n, перенесем остальные слагаемые в другую часть неравенства:

1 (l + 1)2 (k 2 - 2k - 15) + 20(l + 1)(k + 3) + 4 - 32k 16 (3) Оценим правую часть неравенства (3) другим полным квадратом: 2 + (l + 1)(k + 3) n- 4 1 (l + 1)2 (k 2 - 2k - 15) + 20(l + 1)(k + 3) + 4 - 32k 16 1 ((l + 1)(k - 1) + 6) 16
2

2

(4)

Для этого умножим неравенство (4) на 4, перенесем все в большую часть, приведем подобные слагаемые, сгруппированные по степеням l + 1, разложим все в произведение двух неотрицательных сомножителей:

4(l + 1)2 - 2(l + 1)(k + 9) + 8(k + 1) = (2l + 2 - (k + 1)) ћ (2l + 2 - 8)
17

0

(5)


так как из k

2иl

k + 1 следует 2l + 2 - 8 0 и 2l + 2 - (k + 1) 0.

Доказав неравенство (4), заметим, что для неравенства (3) достаточно доказать неравенство больших частей (3) и (4), то есть что

n-

2 + (l + 1)(k + 3) 4
(l+1)(k+1) 2

1 ((l + 1)(k - 1) + 6) 4 + 2 и верно, так как

(6)

Это равносильно неравенству n

(l + 1)l + 2. 2 Итак, доказано неравенство (3) и равносильное ему неравенство (1). l k+1 и n

Утверждение 11. Для всех натуральных чисел
k2 + k +3 2 рассматриваются все наборы из n прямых на проективной плоскости RP2 , в которых не более k прямых пересекаются в одной точке и есть ровно одна точка пересечения k прямых. Прямые каждого рассматриваемого набора делят плоскость RP2 хотя бы на (k + 1)(n - k ) областей. Удалим любую из k прямых, пересекающихся в одной точке. Останется n - 1 прямых, из которых не более k - 1 пересекаются в одной точке, причем есть точка пересечения k - 1 прямых. После удаления прямой число областей плоскости RP2 уменьшилось. По утверждению 7 для набора n - 1 прямых число областей разделенной ими проективной плоскости не меньше k 5, n 2 (n - 1)2 - (n - 1) + 2(k - 1) (k - 1) + 3

По утверждению 10 для чисел

k - 1,
взятых вместо чисел

k(

5),

n - 1(

k2 + k + 2), 2 l2 + l + 2), 2

k(
верно неравенство

4),

l(

k + 1),

n(

2

(n - 1)2 - (n - 1) + 2(k - 1) (k - 1) + 3

(k + 1)(n - k ).

Поэтому исходные n прямых делят проективную плоскость более чем на (k + 1)(n - k ) областей.

18


Теорема 1. (а) Все n-достижимые числа содержатся в множестве
dn -1

[(k + 1)(n - k ); (k + 1)(n - k ) +
k=0

k (k - 1) ] 2

[(dn + 1)(n - dn ); 1 +

n(n - 1) ] 2

()

где dn = [ 2n - 5 3 - 1 ] при n 3 и d1 = d2 = 0. 4 2 (б) Все натуральные числа множества
dn -1

[(k + 1)(n - k ); (k + 1)(n - k ) +
k=0

k (k - 1) ] 2

[(dn + 1)(n - dn ); 1 +

n(n - 1) ] 2

()

являются n-достижимыми. Обозначим множество достижимых чисел, приведенное в теореме, за Mn . Случаи n = 1, 2, 3 разбираются на основе того, что: 1) одна прямая плоскость RP2 делит на одну область, 2) две прямые пересекаются в одной точке, 3) три прямые или все пересекаются в одной точке, или пересекаются в трех точках. dn - 1 по При n 4 пункт (б) следует из утверждений 3 и 4, так как n 2 2 замечанию про число dn и по неравенству dn + dn + 6 4dn - 4. Докажем пункт (а) при n 4. Возьмем любое n-достижимое число m и выберем любой набор , состоящий из n прямых, делящий плоскость RP2 на m частей. По - утверждению 1 верно n m 1 + n(n2 1) . Предположим, что число m не принадлежит множеству Mn . Тогда найдется натуральное число j, 1 j dn , такое что (j - 1)(j - 2) j (n - j + 1) + < m < (j + 1)(n - j ) (1) 2 Тогда по утверждению 5 нет j + 1 прямых из выбранного набора , пересекающихся в одной точке. Обозначим максимальное количество прямых (набора ), пересекающихся в одной точке, за k , тогда 2 k j. Разберем три случая. (а) Верно j k + 1. По утверждению 7 для набора прямых получим

m
По утверждению 10 для чисел

f (n, k )

2

n2 - n + 2k k+3

(2)

k,
верно

j(

k + 1),

j2 + j n( > + 2) 2 (3)

n2 - n + 2 k (j + 1)(n - j + 1) > (j + 1)(n - j ) k+3 Из неравенств (2), (3) и оценки m сверху по неравенству (1) получаем 2 m > (j + 1)(n - j ) > m,
19 противоречие.


(б) Верно j = k 5. Если среди точек пересечения прямых набора есть хотя бы две точки кратности k , то по утверждению 9 и по правому неравенству (1) получается m (k + 1)(n - k ) > m противоречие. Если среди точек пересечения прямых набора есть только одна точка пересечения k прямых, то по утверждению 10 и оценке m сверху по неравенству (1) получается m (k + 1)(n - k ) > m противоречие. (в) Верно j = k = 2, 3, 4. Для каждого варианта k = 2, k = 3, k = 4 оценим m по утверждению 7 (применять можно, так как n k + 1)

m

f (n, k )

2

n2 - n + 2k k+3

Покажем для каждого k = 2, 3, 4, что

2

n2 - n + 2k k+3

(k + 1)(n - k )

(4)

умножая неравенство (4) на k+3 и получая квадратный трехчлен относительно n, 2 2+ неотрицательный при n k 2 k : 2 k = 2, n 6, m f (n, 2) 2 n -5n+4

2 k = 3, n

n2 - n + 4 5 9, m

3n - 6 n2 - 8.5n + 19 = (n - 4)(n - 4.5) + 1 2
n2 -n+6 6

0

f (n, 3)

n2 - n + 6 3 k = 4, n 2 13, m f (n, 4)

4n - 12 n2 - 13n + 42 = (n - 6)(n - 7) 2
n2 -n+8 7

0

n2 - n + 8 7

5n - 20 n2 - 18.5n + 78 = (n - 6)(n - 13) +

n 2

0

Во всех разобранных случаях (а), (б) и (в) получили неравенство

m

(j + 1)(n - j ),

противоречащее правому неравенству (1). Значит, предположение о том, что nдостижимое число m не принадлежит множеству Mn , неверно. Совокупность пунктов (а), (б) теоремы 1 доказывает, что все n-достижимые числа это все натуральные числа множества Mn .

1.4 Обзор работ предшественников. Деление плоскости R2 на области m прямыми эквивалентно делению ной проективной плоскости RP2 на области n = m + 1 прямыми, так как прямых на плоскости R2 можно добавить бесконечно удаленную прямую, любую прямую из набора m + 1 прямых на RP2 можно рассмотреть как удаленную для некоторой плоскости R2 RP2 .
20

вещественк набору m и наоборот, бесконечно


В.И. Арнольд в [Арн08] поставил задачу об определении количеств областей, на которые набор n проективных прямых (различных) может разделить проективную плоскость RP2 . Имелись в виду двумерные области, отрезки прямых и точки пересечения не учитывались. Им были доказаны следующие факты: 1) минимально возможное количество равно n; - 2) максимально возможное количество равно 1 + n(n2 1) ; 3) на все числа из некоторых отрезков подряд идущих натуральных чисел плоскость RP2 может быть разделена (n прямыми), первый отрезок есть число n, второй число 2n - 2, третий пара чисел {3n - 6, 3n - 5}); 4) на числа из промежутков между первым и вторым, а также между вторым и третьим отрезками плоскость RP2 не может быть разделена; 5) на числа из промежутков между наборами с номерами i и i + 1 при всех достаточно больших n (примерно 2i2 и более) плоскость RP2 не может быть разделена. При этом отрезок возможных чисел определяется своим номером и числом прямых n. Рассмотренные В.И. Арнольдом отрезки с номерами, начиная с некоторого (примерно 2n) начинали пересекаться между собой и не доходили до верхней оцен2 - ки 1 + n(n2 1) (отрезки доходили примерно до 3n ) Оставалось неясным для каждого 8 n > 8 возможны ли дыры (между отрезками) с номерами от n до 2n. То есть при2 мерно половина дыр (для каждого n) были не исследованы. Ограниченность результатов В.И. Арнольда (первые две дыры и реализация части возможных количеств) объясняется использованием комбинаторных рассуждений без геометрических. Задача (не о всех, а только) о максимальных и минимальных возможных количествах областей R2 и R3 при делении прямыми и плоскостями рассматривалась Д. Пойа в [Пой75] и О.Е. Акимовым в [Аки03] (обзорно). Было сформулировано обобщение для Rk и линейная зависимость количеств областей Rk при делении n гиперплоскостями с областями Rk при делении n - 1 гиперплоскостью и областями Rk-1 при делении n - 1 гиперплоскостью. Д. Гильберт и С. Кон-Фоссен в [ГКФ81] рассматривают плоские и пространственные конфигурации. Плоская конфигурация это набор точек и прямых (на R2 ), каждая из точек и прямых инциндентна одинаковому для всех (и точек и прямых) числу прямых и точек этого набора. Пространственная конфигурация состоит из точек и плоскостей с аналогичным свойством. Простейшей плоской конфигураией является выпуклый многоугольник, то есть набор вершин и прямых, содержащих его стороны. В качестве примеров в [ГКФ81] приведены все конфигурации с не более, чем 9 прямыми, теоремы Дезарга и Брианшона, кривые третьего порядка. Задача Сахарова. В Rk есть n гиперплоскостей общего положения, среднее число i-мерных граней у областей в пределе при n такое же, как и у k -мерного куба, i то есть Ck 2k-i .

1.5 Уточнения некоторых доказанных ранее утверждений. Обозначение: Для целых чисел
k 2, 0 i k-2 и n 2k - i - 1
за f (n, k , k - i) обозначим минимально возможное число областей плоскости RP2 , разделенной n прямыми с двумя свойствами: (а) есть точка пересечения кратности k , 21


(б) все остальные точки пересечения имеют кратности k - i и меньше, причем среди них есть точка кратности k - i.

Утверждение 12. Для всех целых чисел
k 2, 0 i k-2 и n 1 + (k + 1)(k - i - 1)

верно неравенство

f (n, k , k - i)

(k + 1)(n - k ).

Рассмотрим любой набор n прямых со свойствами из обозначения f (n, k , k - i). За aj обозначим количество точек пересечения кратности j для j = 2, 3, . . . , k . Если i > 0, то

ak = 1, a

k -1

= ћ ћ ћ = ak

-i+1

= 0, a

k -i

1,

поэтому число пар прямых равно

n(n - 1) = 2
Поэтому
k

k

aj
j =2

j (j - 1) k (k - 1) = + 2 2

k-i

a
j =2

j

j (j - 1) . 2

aj (j - 1) = f (n, k , k - i) - 1
j =2

n(n - 1) k + (k - 1) 1 - k-i k-i

.

Если i = 0, то

n(n - 1) = 2
следовательно

k

a
j =2

j

j (j - 1) , 2

n(n - 1) . k Из обеих оценок получаем, что для любого 0 i k - 2 верно неравенство f (n, k , k - i) - 1 f (n, k , k - i)
Осталось доказать неравенство

n(n - 1) (k - 1)i - + 1. k-i k-i

n(n - 1) (k - 1)i - + 1 (k + 1)(n - k ). k-i k-i Неравенство квадратичное относительно n, домножая обе части на k - i, выделяя полный квадрат и группируя правую часть, получаем неравенство: n- 1 + (k + 1)(k - i) 2
2

(k + 1)2 (k - i)(k - i - 4) + 6(k + 1)(k - i) + k (i - 1), 4
22


которое проверяется подстановкой

1 + (k + 1)(k - i - 1)

вместо

n

и раскрытием квадрата в левой части по степеням (k + 1) и (k - i).

Утверждение 13. Возьмем натуральные числа a b 2 и m 1. На евклидовой плоскости R2 рассмотрим a попарно параллельных прямых, b прямых, попарно
параллельных и перпендикулярных всем a прямым, еще c прямых, не параллельных ни первым a, ни следующим b прямым. За
k

s=
j =2

aj (j - 1)

обозначим сумму уменьшенных на 1 кратностей точек пересечения всех a + b + c прямых между собой, где aj это количество точек кратности j. Тогда верно неравенство

s
2

2c(a + b) 2ab + a + b - 3 + . 3 3

Занумеруем a прямых и b прямых по порядку их расположения на плоскости R и для каждого 1 i aи1 j b точкой Aij назовем точку пересечения прямых с номерами i, j. Для каждой прямой l из c прямых за tl обозначим количество лежащих на ней точек Aij . Количество точек пересечения этой прямой с a + b прямыми, отличных от Aij , равно a + b - 2tl . Если эта прямая не проходит через пару точек A1b , Aa1 или пару A11 , Aab , то количество пар лежащих на прямой различных точек Aij , между которыми нет точек пересечения этой прямой с a + b прямыми, не менее

(tl - 1) - (a + b - 2tl - 1).
Если прямая проходит через одну из двух пар точек, то количество не менее

(tl - 1) - (a + b - 2tl ).
Обозначим сумму про всем c прямым этих количеств за T . С другой стороны, любая пара точек Aij без точек a + b прямых между ними есть диагональ какого-то из (a - 1)(b - 1) прямоугольников

Aij A(i

+1)j

A(i+1)(

j +1)

Ai(j

+1)

для

1

i

a - 1, 1

j

b - 1.

Каждая пара точек принадлежит не более, чем одной из c прямых, поэтому складывая оценки количеств по всем c прямым, получим неравенство:
c

2(a - 1)(b - 1)
Рассмотрим отдельно два случая. (1) Верно неравенство

T

-2 +
l=1

(3tl - (a + b)) .

()

23


T > (a - 1)(b - 1).
По принципу Дирихле хотя бы в T -(a-1)(b-1) прямоугольниках Aij A(i+1)j A(i+1)(j +1) Ai обе диагонали являются отрезками каких-то из c прямых. Оценим сумму s, посчитав пересечения a прямых с b прямыми как ab, пересечения c прямых с a + b прямыми как c
(j +1)

a + b - tl ,
l=1

и диагоналей прямоугольников как T - (a - 1)(b - 1) и сложив в неравенство
c

s

ab +
l=1

(a + b - tl ) + T - (a - 1)(b - 1).

Умножим последнее неравенство на 3 и сложим с неравенством (), получим

3s

2c(a + b) + 2T - 3(a - 1)(b - 1) + 3ab - 2.

Заменяя T по неравенству

T
и деля обе части на 3, получим неравенство

(a - 1)(b - 1) + 1

s
(2) Верно неравенство

2c(a + b) 2ab + a + b - 1 + . 3 3

T
Аналогично случаю (1) оценим

(a - 1)(b - 1).

c

s

ab +
l=1

(a + b - tl ),

умножим оценку на 3 и сложим с неравенством (), получим

3s
Заменяя T по неравенству

2c(a + b) + 3ab - 2 - T .

T
и деля обе части на 3, получим

(a - 1)(b - 1)

2c(a + b) 2ab + a + b - 3 + . 3 3 Оба случая дали требуемую оценку на s. s

Утверждение 14. Для всех целых чисел
24


k

5,

1

j

[

k-2 ], 3

0

i

[

k - 2 - 3j ]иn 2

(k + j )(k + j - 1) +3 2

верно неравенство

f (n, k , k - i)

(k + j )(n - k - j + 1).

Рассмотрим n прямых со свойствами из определения f (n, k , k - i), делящих плоскость RP2 на f (n, k , k - i) областей. По свойствам (а) и (б) существуют различные точки пересечения A и B кратностей k и k - i соответственно. Возможны два случая: Случай (1). Каждая из n прямых не содержит одновременно точек A и B . Выделим в проективной плоскости RP2 евклидову плоскость R2 так, чтобы обе точки A и B оказались бы на бесконечности, а прямые, проходящие через точку A, оказались бы перпендикулярны прямым, проходящим через точку B . Применим утверждение 13 с

a = k,

b = k - i,

c = n - 2k + i

к прямым, проходящим через точки A, B и к остальным прямым. Возможность применения утверждения 13, то есть неравенства

a=k

2,

b=k-i

k +1 2

2 и c = n - 2k + i

k2 + k + 3 - 2k 2

1

следуют из условия k единицу, то есть

5. Для оценки f (n, k , k - i) добавим вклад точек A, B и s + (k - 1) + (k - i - 1) + 1

f (n, k , k - i)
и получим оценку

2 1 n (2k - i) - 2k (k - i) + -2i2 + 8k - 4i - 6 3 3 Осталось доказать неравенство для правой части (1): f (n, k , k - i) 1 2 -2i2 + 8k - 4i - 6 n (2k - i) - 2k (k - i) + 3 3

(1)

n(k + j ) - k 2 + k + j (1 - j - 2k )

сократим обе части на nk - k 2 + k , перенесем слагаемые с n в большую, а без n в меньшую части неравенства, сделаем замену

k - 2i = 3j + u
и получим

nu 3

k-

2 3

u+

2i2 + (j - 1)(k - j - 2). 3
25


Перенесем (k - 2 )u в большую часть неравенства и заметим, что 3

2i = k - 3j - u
заменим n на не большее его число



u

2,

(k + j )(k + j - 1) + 3, 2
а u в большей части неравенства на 2, заменим 2i2 на не меньшее число домножим обе части на 3 и получим неравенство
(k-3j -2)2 2

,

k 2 + 3j 2 - 5k + 3j + 8. 2 Перенесем все в большую часть, приведем подобные слагаемые и заметим, что k 2 + 2k j + j 2 - 7k - j + 10 k2 - j 2 2, 2k j - 2k - 4j + 2 -2. 2 k Это верно при j , k 5. Случай (1) рассмотрен. 3 Случай (2). Одна из n прямых (назовем е? l1 ) проходит через обе точки A, B . Выделим в проективной плоскости RP2 евклидову плоскость R2 = RP2 \l1 так, что k - 1 прямых, проходящие через точку A, перпендикулярны k - i - 1 прямой, проходящей через точку B . Применим утверждение 13 с a = k - 1, b = k - i - 1, c = n - 2k + i + 1

к прямым, проходящим через точки A, B и к остальным прямым, кроме удаленной на бесконечность прямой l1 . Возможность применения утверждения 13, то есть неравенства

a=k-1

2,

b=k-i-1

k 2

2 и c = n - 2k + i + 1

k2 + k + 3 - 2k 2

1

следуют из условия k 5. Для оценки значения f (n, k , k - i) добавим вклад точек пересечения прямой l1 с остальными прямыми и единицу, получим

(4k - 2i - 1) 1 - 2k (k - i) + -2i2 + 10k - 5i - 7 3 3 Осталось доказать неравенство для правой части (2): f (n, k , k - i) n (4k - 2i - 1) 1 - 2k (k - i) + -2i2 + 10k - 5i - 7 3 3

(2)

n

n(k + j ) - k 2 + k + j (1 - j - 2k ).

Cократим обе части неравенства на nk - k 2 + k , сделаем замену

k - 2i - 1 = 3j + u,
домножим обе части неравенства на 3 и перенесем слагаемые с n и u в большую, а остальные в меньшую части неравенства: 26


(n + 7 - 3k )u

(2i - 9)i + (3k j - 3j 2 - 18j ).

Подставим вместо n не большее его число (k+j )(k+j -1) + 3, вместо i = k-32j -u , 2 перенесем все в большую часть, приведем подобные слагаемые и выделим множитель u-1:

(u - 1)

k 2 - 5k + 2

j2 + 4 - 2j 2

+ kj -

3j + u 2

+ k (j + 3) - (j + 1)

2

0.

Осталось заметить, что все сгруппированные выражения не меньше нуля:

u-1 kj -

0,

k 2 - 5k 2

0,

j2 + 4 - 2j 2

0,

3j + u 0, k (j + 3) - (j + 1)2 0, 2 что и завершает доказательство случая (2), а значит и утверждения 14.
венство

Утверждение 15. Для всех натуральных чисел k
f (n, k )

4, n
2

k + 1 верно нера(1)

2n2 + (2k 2 - 4k - 2)n - 2k 3 + 6k 3k - 1

Рассмотрим любой набор из n прямых, в котором не более k прямых пересекаются в одной точке, и набор прямых делит плоскость RP2 на f (n, k ) областей. Выберем какую-то точку пересечения кратности k и обозначим е? буквой O, а k прямых, проходящих через не?, обозначим по порядку l1 , . . . , lk . Остальные n - k прямых назовем оставшимися. Эти k прямых делят плоскость RP2 на k долей, рассмотрим каждую долю (ограниченную прямыми li и li+1 , считаем lk+1 = l1 .) Каждая из оставшихся прямых пересекает долю по отрезку, выберем из этих n - k отрезков максимальное по количеству (обозначим его a) подмножество отрезков, попарно не пересекающихся во внутренних точках. Это подмножество отрезков (с индуцированной из плоскости RP2 топологией) образует граф без циклов (то есть лес несвязное объединение деревьев). Действительно, через точку O и через долю можно провести (мысленную) прямую и упорядочить отрезки подмножества по порядку (любому из двух, считая от точки O) следования их точек пересечения с (мысленной) прямой. Тогда оба конца первого по порядку отрезка предполагаемого цикла суть концы двух других отрезков цикла, располагающихся по одну сторону доли от первого отрезка и, следовательно, пересекающихся во внутренней точке. В графе без циклов число ребер не превосходит уменьшенного на единицу числа вершин. Вершины графа располагаются на прямых li и li+1 , поэтому a + 1 не превосходит числа точек пересечения прямых li и li+1 с оставшимися (n - k ) прямыми. Каждый из n - k - a отрезков, не вошедших в подмножество, пересекает хотя бы один из отрезков подмножества во внутренней точке (иначе добавили бы его в подмножество). Поэтому n - k - a не превосходит суммы (по точкам пересечения прямых, расположенных строго внутри доли) уменьшенных на единицу кратностей, то есть

27


k

n-k-a
j =2

ai (j - 1) j

(2)

где за ai j прямыми li и За cj для положенных равенство

обозначено количество точек пересечения кратности j в доли между li+1 . j = 2, . . . , k обозначим количество точек пересечения кратности j, расна прямых l1 , . . . , lk , кроме точки O. Тогда по утверждению 2 верно
k k k

f (n, k ) =
i=1 j =2 k i=1

ai j

(j - 1) +
j =2

cj (j - 1) + k

(3)

так как cj + ai это количество точек пересечения на плоскости RP2 кратj ности j, отличных от точки O. Заметим, что
k

cj (j - 1) = k (n - k )
j =2

(4)

так как каждая из оставшихся прямых пересекается с каждой из k прямых l1 . . . , lk . Из равенств (3) и (4) следует:
k k

f (n, k ) - k (n - k + 1) =
i=1 j =2

ai (j - 1) j

(5)

Сложим неравенства (1) и (2) и сложим результаты по всем i = 1, . . . , k , получим
k k

k (n - k + 1)
i=1 j =2

ai (j - 1) + 2(c2 + ћ ћ ћ + ck ) j

(6)

Подставим в (6) равенство (5) и выразим f (n, k ) :

f (n, k )

2k (n - k + 1) - 2(c2 + ћ ћ ћ + ck )
k-1

(7)

Обозначим сумму c2 + ћ ћ ћ + c

буквой s. Из равенства (4) и неравенства
k-1

c2 + 2c3 + ћ ћ ћ + (k - 2)c
имеем неравенство:

s

k (n - k ) - s k-1 Подставим (8) в (7), используя сумму s : c
k

(8)

f (n, k )

2k (n - k + 1) - 2s -

2s 2k (n - k )(k - 2) k-2 2k (n - k ) + = + 2k - 2s (9) k-1 k-1 k-1 k-1

По утверждению 6 верно неравенство 28


n(n - 1) k - 2 + s (10) k k Умножим неравенство (9) на k - 1, неравенство (10) на 2k и сложим, чтобы получить неравенство на f (n, k ) без суммы s : f (n, k ) 1+ (3k - 1)f (n, k ) 2k (n - k )(k - 2) + 2k 2 + 2n(n - 1) (11)

Откуда получаем требуемое неравенство

f (n, k )

2n2 + (2k 2 - 4k - 2)n - 2k 3 + 6k 3k - 1

2

Обозначение. За Fm (n) (и за fm (n)) обозначим максимальное (и минимальное) число областей пространства Rm при делении n гиперплоскостями (размерности гиперплоскостей m - 1, размерности частей m.)
Формулировка следующего утверждения 16 принадлежит О.Е. Акимову (см. [Аки03], 4.1, таблица 4.6)

Утверждение 16.
m m m n n m 1 = fm (n) = n + 1 = = = = 1 = Fm (n) = n + 1 - 2 = Fm (n) = 1 + n(n2 1) 1 = Fm (1) = 2 2, m 2 = Fm (2) = 4 2, n 2 = Fm (n) = Fm (n - 1) + Fm-1 (n - 1)

Докажем неравенство Fm (n) Fm (n - 1) + Fm-1 (n - 1). Из данных n гиперплоскостей возьмем n - 1, они делят пространство Rm не более, чем на Fm (n - 1) областей. Проведем оставшуюся гиперплоскость, она разделит на две те m-мерные области пространства Rm (от деления n - 1 гиперплоскостью), через которые она проходит. Каждая m-мерная область порстранства Rm (от деления n - 1 гиперплоскостью), пересекающаяся с оставшейся гиперплоскостью, высекает на гиперплоскости m - 1-мерную область, причем число таких областей не превосходит Fm-1 (n - 1), так как они образуются при делении оставшейся гиперплоскости не более чем n - 1 плоскостью размерности n - 2, образованными пересечением n - 1 гиперплоскостью с оставшейся гиперплоскостью. Поэтому число раздвоенных областей пространства Rm не превосходит Fm-1 (n - 1), что и доказывает неравенство Fm (n) Fm (n - 1) + Fm-1 (n - 1).

29


2. Мощность отделяемого множества вершин многомерного куба.
. Будем писать, что касательная гиперплоскость к сфере отделяет вершину куба A, если вершина A и центр сферы находятся строго по разные стороны от гиперплоскости .

2.1 Формулировка и мотивация гипотезы. Обозначение. Рассмотрим n-мерный куб и вписанную в него n - 1-мерную сферу

Гипотеза (А.Бен-Таал, А.Немировский, К.Рос, [B N R02], (А.2)). Любая касательная гиперплоскость к вписанной сфере отделяет не более чем 2n-2 вершин n-мерного куба. Пример 1. Пусть координаты вершин n-мерного куба будут равны
(+1, +1, . . . , +1) Rn .
Тогда вписанная сфера задается уравнением x2 + x2+ ћ ћ ћ + x2 = 1. Гиперплоскость 1 2 n y1 + y2 = 2 касается вписанной сферы в точке ( 22 , 22 , 0, . . . , 0). Касательная гиперплоскость отделяет 2n-2 вершин куба, в точности те, у которых первые две координаты равны +1. Авторы [B N R02] доказали (лемма А.1), что любая касательная гиперплоскость к 1 вписанной сфере отделяет не более чем 1 2n вершин n-мерного куба. Оценки 3 2n им 3 было достаточно для получения содержательных результатов в следующей области. Методология Robust оптимизации (развитая авторами [B N 98]) сводит N P трудные задачи нахождения минимума семейства линейных функций на выпуклых множествах при неявных ограничениях сводит к разрешимым задачам, увеличивая количество неявных ограничений. Например, рассматривается задача поиска
xR

min {cT x : n

Ax - b LN , (A, b, c) U }, zN
2 2 z1 + ћ ћ ћ + zN

() },

где

LN

это
N Чn

N -мерный конус LN = {z RN :

-1

а матрицы A R

, векторы b RN , c Rn берутся из множества параметров
L

U =

(A, b, c) = (A , b , c ) +
l=1

0

0

0

yl (Al , bl , cl ) :

y T Qk y

1, k = 1, . . . , K

для фиксированного набора неотрицательно определенных матриц Qk RLЧL , вектора y = (y1 , . . . , yL ) RL , лежащего в пересечении K эллипсоидов и вещественного числа R. Задача (*) для = 1 N P трудна (см. [B N 98]), но она аппроксимируется (см. [B N R02]) задачей (*) для > 1, которая уже вычислима. Согласно [B N R02], уровень аппроксимации ограничивается неравенством



2ln

2 1 - 2r
30

K

Rank (Qk )
k=1

.


Константа r это максимальное относительное количество вершин n-мерного куба, отделяемых касательными гиперплоскостями к вписанной сфере. То есть любая касательная гиперплоскость отделяет не более, чем r2n вершин куба.

2.2 Доказательства частных случаев гипотезы.
Обозначим координаты вершин n-мерного куба за

(a1 , . . . , an ),

где |ai | = 1, i = 1, . . . , n.

Обозначим координаты точки касания гиперплоскости и вписанной сферы за (x1 , . . . , xn ). Радиус вписанной сферы равен 1, поэтому x2 + ћ ћ ћ + x2 = 1. Уравнение касательной 1 n гиперплоскости имеет вид

x1 y1 + x2 y2 + ћ ћ ћ + xn yn = 1,
где переменными являются y1 , . . . , yn . Касательная гиперплоскость отделяет вершину куба с координатами (a1 , . . . , an ) тогда и только тогда, когда
n

a1 x1 + ћ ћ ћ + an xn > 1.
i=1

Пример 2. Для натурального числа k

рассмотрим гиперплоскость 3k - 2 3 3 y1 + y2 + ћ ћ ћ + y2k = 1. 3k - 1 3k - 1 3k - 1

n 2

Точка касания гиперплоскости и сферы имеет координаты: 3k - 2 3 3 , ,..., , 0, . . . , 0 . 3k - 1 3k - 1 3k - 1 Вершина куба с координатами (a1 , . . . , an ) отделена гиперплоскостью тогда и только тогда, когда a1 = 1 и среди чисел a2 , a3 , . . . , a2k есть не менее k единиц. "Только тогда" следует из неравенств 3 3 3 3k - 2 3 a2 + ћ ћ ћ + a2k и + > 1. 3k - 1 3k - 1 3k - 1 3k - 1 3k - 1

"Тогда" следует из неравенств 3 3 a2 + ћ ћ ћ + a 3k - 1 3k - 1


2k

3(2k - 1) 3k - 1

1+

3k - 2 , 3k - 1
2k

то есть у отделенной вершины первая координата a1 = 1 и среди чисел a2 , . . . , a более половины положительных. Всего эта гиперплоскость отделяет 2n-2 вершин куба.

6 любая касательная гиперплоскость к вписанной сфере отделяет не более 2 вершин куба. То есть для всяких n 6 2 2 2 чисел x1 , x2 , . . . , xn со свойством x1 + x2 + ћ ћ ћ + xn = 1 количество N (x) наборов n чисел
n- 2

Теорема 2. Для n-мерного куба при n

31


a1 , a2 , . . . , an , каждое из которых равно +1 или -1, таких, что a1 x1 + a2 x2 + ћ ћ ћ + an xn > 1, не превосходит 2n-2 . При n 5 добавим фиктивные числа xn+1 = xn+2 = ћ ћ ћ = x6 = 0 и сведем теорему 2 к случаю n = 6. При замене знаков у чисел xi количество N (x) наборов 6 чисел a1 , . . . , a6 , каждое из которых +1 или -1, таких, что a1 x1 + a2 x2 + a3 x3 + a4 x4 + a5 x5 + a6 x6 > 1, не изменится. Поэтому считаем x1 , . . . , x6 0. Фиксируем и упорядочим числа x1 x2 x3 x4 x5 x6 0. Назовем набор 6 чисел a1 , . . . , a6 искомым, если каждое из них равно +1 или -1 и верно неравенство a1 x1 + a2 x2 + a3 x3 + a4 x4 + a5 x5 + a6 x6 > 1. Рассмотрим три случая:

Случай (а). Верно неравенство
- x1 + x2 + x3 + x 4 + x5 + x
6

1.

Для всякого искомого набора a1 , . . . , a6 имеем a1 = 1. Верно неравенство
6

x1 +
i=2

(-ai )xi < 1,

так как иначе получим противоречие:
6 6

2

2x1 = (a1 + 1)x1 =
i=1

ai x

i

+

x1 +
i=2

(-ai )x

i

> 1 + 1 = 2.

Поэтому число искомых наборов N (x) не превосходит половины от количества всевозможных наборов из 5 чисел a2 , . . . , a6 +1 или -1 каждое, т.е. N (x) 16. Случай (а) разобран. Теперь, исходя из неравенства

-x1 + x2 + x3 + x4 + x5 + x6 > 1,
получим следующие неравенства (используемые в оставшихся случаях). Применим неравенство Коши-Буняковского к числам x1 , x2 , x3 , x4 и получим

x1 + x2 + x3 + x 4
поэтому верны неравенства:

4

x2 + x2 + x2 + x 1 2 3 4

2 4

1 , 2

x1 + x2 + x3 + x
Предположив выполнение неравенства

4

2 и x2 + x

4

1.

x1 + x2 - x3 + x4 - x5 - x

6

1

и сложив его с исходным (для случаев (б) и (в)) неравенством

-x1 + x2 + x3 + x4 + x5 + x6 > 1,
получим противоречие с неравенством x2 + x
4

1, откуда получаем, что

x1 + x2 - x3 + x4 - x5 - x6 < 1
32


и что существует не более одного искомого набора, содержащего не -1. Этот (гипотетически возможный) набор a1 = a2 = a3 = 1, a4 = Отметим, что искомых наборов с не более, чем одной -1, ровно 7 наборов 6 чисел с не более, чем одной -1, ровно 7), и для оценки наборов N (x) осталось рассмотреть искомые наборы с двумя -1. Случай (б). Верны неравенства

менее чем три a5 = a6 = -1. (так как всего числа искомых

-x1 + x2 + x3 + x4 + x5 + x6 > 1 и

- x1 + x2 + x3 + x4 + x5 - x

6

1.

Предположив дополнительно выполнение неравенства

x1 - x2 + x3 - x4 + x5 + x6 > 1
и огрубив предположенное до x1 + x6 > 1, перемножим два следующих неравенства,

x6 > 1 - x

1

и

x2 + x3 + x4 + x5 + x6 > 1 + x1 , 1 - x2 = x2 + ћ ћ ћ + x 1 2
2 6

получим строгое неравенство

x6 (x2 + ћ ћ ћ + x6 ) > 1 - x2 . 1

Противоречие привело к системе неравенств:

- x1 + x2 + x3 + x4 + x5 - x

6

1 и x1 - x2 + x3 - x4 + x5 + x

6

1,

откуда искомых наборов с двумя -1 не более 8. Перечислим все (гипотетически возможные) искомые наборы с двумя -1 :

a2 = a5 = -1; a3 = a6 = -1;

a2 = a6 = -1; a4 = a5 = -1;

a3 = a4 = -1; a4 = a6 = -1;

a3 = a5 = -1; a5 = a6 = -1.

Сложим оценки количеств искомых наборов, содержащих не более одной, ровно две и хотя бы три -1, получим N (x) 7 + 8 + 1 = 16. Случай (в). Верны неравенства

- x1 + x2 + x3 + x4 + x5 + x6 > 1 и

- x1 + x2 + x3 + x4 + x5 - x6 > 1.

Предположив дополнительно выполнение неравенства

x1 + x2 - x3 + x4 - x5 + x
и сложив его с исходным в случае (в) неравенством

6

1

-x1 + x2 + x3 + x4 + x5 - x6 > 1,
получим противоречие с неравенством x2 + x4 1. Поэтому искомых наборов с двумя -1 не более 6. Перечислим все (гипотетически возможные) искомые наборы с двумя -1:

a1 = a6 = -1; a4 = a5 = -1;

a2 = a6 = -1; a4 = a6 = -1;
33

a3 = a6 = -1; a5 = a6 = -1.


Сложим оценки количеств искомых наборов, содержащих не более одной, ровно две и хотя бы три -1, получим N (x) 7 + 6 + 1 = 14.

Замечание. Гиперплоскость
точке с координатами (
1 1 , n n

,...

1 1 y1 + y2 + ћ n n 1 , n ), отделяет

1 ћ ћ + n yn = 1, касающаяся сферы в i ровно i< n-n Cn вершин куба.
2

Пусть координаты отделяемой вершины куба состоят из k единиц и n - k минус единиц, тогда k - (n - k ) > n, то есть n - k < n-2 n . Осталось заметить, что n существует Cn -k вершин куба с ровно n - k отрицательными координатами.
1 1 1 3 гиперплоскость n y1 + n y2 + ћ ћ ћ + n yn = 1 отделяет менее, чем 2n-2 вершин n-мерного куба. То есть (используя замечание) для всех натуральных чисел n 3 верно неравенство: i Cn < 2 n-2

Теорема 3. Для n

.

0 i<

n- n 2

План доказательства: для 3 n 15 вычислим обе части неравенства явно. k Для n 16 перепишем неравенство через сумму "центральных" Cn , оценим последние по формуле Стирлинга, а их сумму через
i чества участвующих в суммировании Cn для 3

e- 2 dt. n 15 :

t

2

Шаг 1. Составим таблицу из обеих частей неравенства и числа


n- n 2

коли-

n- n 2 i Cn n-2

n

2

3 1 1 2

4 1 1 4

5678 9 10 11 12 13 14 15 2233 3 4 4 5 5 6 6 6 7 29 37 46 176 232 794 1093 3473 4944 8 16 32 64 128 256 512 1024 2048 4096 8192

За x и x обозначим верхнюю и нижнюю целые частичисла x соответственно. n+ n n- n i n-i Для n 16, пользуясь соотношениями Cn = Cn и n - = , перепишем 2 2 требуемое неравенство:
n+ n 2 i Cn > 2n-1 .

i=

n- n 2

где 0

i Шаг 2. Оценим Cn снизу, используя формулу Стирлинга n! = ( n )n ћ ( 2 n e e



n 12n



n

1, и функцию энтропии H (x) = -x log2 x - (1 - x) log2 (1 - x) : 2 n ћe 2 i 2 (n - i) n - ћe 4i(n - i)
n-i n - i- 12n 12i 12(n-i)

),

i Cn

ni ћ nn-i n! =i = i!(n - i)! i ћ (n - i)n 2nH
i () n

-i

ћ

ћ

2 ћ

1 n ћ 3 4i(n-i)

.

Введем величину t =

i n

1 - 2 , выразим через нее дробь

34


4 4i(n - i) = n

n 2

+ nt n

n 2

- nt

= n(1-4t2 )

и оценку

i Cn

2

1 nH (t+ ) 2

2 e 3n(1-4t2 ) ћ . n(1 - 4t2 )

-

1

Определим функцию

f (t) := 2

1 nH (t+ )-n 2

ћ

e

2nt2 -



1 3n(1-4t2 ) 2

1 - 4t

на отрезке

|t|

1 , 2n

отрезок получился из неравенства |i - n | 2 степени



n 2

. Преобразуем основание и показатель =e
n 1+2t - ln(1-4t2 )-nt ln( ) 2 1-2t

2nH

1 (t+ )-n 2

=2

1 1 n(-( +t)log2 (1+2t)-( -t)log2 (1-2t)) 2 2

Определим функцию

h(t) := ln(f (t)) = 2nt2 -

1 -nt ln 3n(1 - 4t2 )

1 + 2t n+1 - ln(1-4t2 ) при |t| 1 - 2t 2

1 . 2n

1 . ПроФункция h(t) четная и h(0) = - 31 . Покажем, что h (t) 0 при 0 t n 2n дифференцируем выражение, определяющее функцию h(t), сгруппируем слагаемые и разложим вторую группу слагаемых в ряд по степеням 2t :

h (t) =

2t 8t - 2 1 - 4t 3n(1 - 4t2 )2
2

+ +

2t 1 + 2t + 4nt - n ln( ) 2 1 - 4t 1 - 2t


2t = 1 - 4t

4 1- 3n(1 - 4t2 ) 2t 41 1 - 4t2 45


(2t)
k=0

2k+1

- 2n
l=1

(2t)2l+1 2l + 1 0.

+
k=0

(2t)2

k+1

1-

2n(2t)2 2k + 3

Неравенства верны, так как

1 и n(2t)2 1. 8 Из четности функции h(t) и неотрицательности функции h (t) для 0 получим неравенства: n 16, 0 t h(t) h(0) = - 1 3n
и

t

1 2n

f (t)

f (0) = e-

1 3n

для |t|

1 . 2n

i Отсюда следует оценка Cn снизу: i Cn n

f (t)2

2 -2 e n

nt2

2

n

2 -2 e n

nt2 -

1 3n

,

n при n|t| = |i - | 2



n . 2

35


Шаг 3. Из равенства второй производной (e- 2 ) = (x2 - 1)e-
лость вверх функции e верно неравенство
x2 - 2

x

2

x2 2

получим выпук-

при |x| < 1. Для любого отрезка [a, b], где -1
b

a
1,

e
a

-

x2 2

dx

(b - a)e

-

(a+b)2 8

,

поскольку криволинейная трапеция

(x, y )|a
(a+b)2 8

x

b, 0

y

e-

x2 2

в силу выпуклости содержится в трапеции, отсекаемой касательной к графику y =

e

-

x2 2

в точке

a+b 2

,e

-

от полуполосы {(x, y )|a

x

b, 0

y } . Аналогично

(при b < 2 содержащая трапеция не вырождается в ломаную) получим неравенство
1

e
a

-

x2 2

dx

(b - a)e-

(a+b)2 8

для любых чисел

-1


a<


a+b < 1 < b < 2. 2

Обозначим множество целых чисел отрезка n-2 n , n+2 n за In . Для каждого i1 i индекса i In обозначим число 2 n( n - 2 ) за xi , тогда из оценки Cn снизу в шаге 2 получим неравенство:
i Cn iIn

2

n

2- e n
x2 i 2

1 3n iIn

e

-

x2 i 2

.

Оценим

e-

x2 i 2



снизу:

e-

n 2

1 min{xi + ,1} n

e
1 max{xi - ,-1} n

-

x2 2

dx.

Заметим, что

max

iIn

2 {xi } > 1- , n 1- e 2

min

iIn

2 {xi } < -1+ , n
x
2

и оценим снизу сумму интег

1- i Cn iIn

1 n

2n

1 3n -1+
1 n

e- 2 dx.

Шаг 4. Используя неравенства
e-
x

1 - x при 0

x

1,

<

получим неравенства:

22 7

и

n

16,

e-

1 3n

1-

1 3n

44 , 45
36

1 1 > 2 2

7 11

и


1-

1 n

e
-1+
1 n

-

x2 2

3 4

dx
- 3 4

1-

x2 2

dx =

87 . 64

Поэтому
iIn

i Cn > 2n-

1

77 87 > 2n-1 . 81 80

Комментарий 1. В пределе n сумма биномиальных коффициентов, деленная на 2n , стремится к нормальному (гауссовому) распределению, то есть:
2
-n 0 i<
n- n 2

i Cn

1 2

-1

e
-

-

t2 2

dt 0.158 < 0.25

Комментарий 2. В книге А.Н. Ширяева [3], гл. 3, пар. 11, стр. 475, сформулирована следующая задача (2). Пусть ak независимые одинаково распределенные случайные величины с нулевым математическим ожиданием, фиксированной дисперсией и конечным третьим моментом, то есть E ak = 0, Dak = 2 , E |ak |3 < . Тогда верна оценка отклонения вероятности P от интеграла гауссового распределения:
a1 + ћ ћ ћ + an 1 P( < x) - n 2
x t

e- 2 dt
-

2

cE |a1 |3 . 3 n(1 + |x|)3

Доказав эту задачу с малой константой c и применив ее с x = -1, можно получить еще одно доказательство теоремы 3.

37


3. Серии специальных и ретрагируемых спайнов.
Спайн это двумерный полиэдр с особенностями типа мыльной пленки, получаемый из трехмерного многообразия операцией, похожей на деформационную ретракцию. Существуют разные виды спайнов простые, ложные поверхности, специальные. Какой-нибудь спайн довольно легко получить из триангуляции многообразия путем коллапсирования граничных тетраэдров. Однако у всякого трехмерного многообразия (из замкнутых надо удалить диск) существует специальный спайн. Особенности специального спайна образуют граф степени 4, который является одномерным остовом спайна (как клеточного комплекса). В этом параграфе будут определены и рассмотрены только специальные спайны. Особенно интересны специальные спайны с одной двумерной клеткой (в представлении полиэдра в виде клеточного комплекса). Возможность утолщения такого спайна до ориентируемого многообразия позволяет ввести в многообразии (с краем) метрику пространства Лобачевского, то есть получить гиперболическое незамкнутое многообразие (см [FMP03]). Удалим диск из двумерной клетки, останется полиэдр, ретрагирующийся на свою граничную окружность окружность удаленного диска (см. лемму 3 этого параграфа). Существует много таких специальных спайнов с одной двумерной клеткой как минимум 3(6 2)n-4 , где n число вершин в графе особенностей спайна (см. лемму 2). Окрестность каждой вершины специального спайна гомеоморфна конусу над полным графом из 4 вершин. Окрестность каждой точки ребер графа особенностей специального спайна гомеоморфна конусу над окружностью с диаметром. Результаты этого параграфе получены рассмотрением окрестности графа особенностей с специальном спайне. При этом границы двумерных клеток (семейство окружностей) отображаются на граф особенностей (при построении клеточного комплекса) так, что у каждого ребра графа прообраз состоит из трех отрезков (не обязательно расположенных на разных граничных окружностях). Лемма 1 дает точную оценку (с примером) на максимальное количество двумерных клеток (то есть на количество граничных окружностей) при фиксированном числе вершин специального спайна. Лемма 2 строит 3(6 2)n-4 различных специальных спайнов с одной двумерной клеткой и n вершинами для четного n. В лемме (2) используется только один граф особенностей. Лемма 3 доказывает предположение А.Т. Фоменко о том, что окрестности графов особенностей специальных спайнов ретрагируются на свою границу (границу окрестности).

с петлями и кратными ребрами). Рассматривается семейство циклов C на графе с свойством: 38

3.1 Оценка количества двумерных клеток специальных спайнов. Лемма 1. Дан связный граф G с n вершинами степени 4 каждая (возможно


Каждое ребро графа принадлежит ровно трем циклам и эти три цикла при подходе к вершине переходят на три выходящие из нее ребра, то есть каждый цикл переходит на свое ребро, см. рис. 1. Тогда (а) число циклов в любом семействе не превосходит 2n + 1 при n 3 и не превосходит 2n + 2 при n = 1, 2. (б) Для графов с рис. 2(а) есть семейство из 2n + 1 цикла при n 3 и из 2n + 2 цикла при n = 1, 2. Рис. 2(б) есть доказательство пункта (б) леммы. Докажем пункт (а): Рассмотрим остовное дерево графа G и его окрестность D в графе G, см. рис. 3. Рассмотрим пересечение семейства циклов с графом D это семейство I из 3n + 3 отрезка. Рассмотрим тройку циклов, имеющих общую висячую вершину остовного дерева. Хотя бы 2 из них содержат по крайней мере по 2 отрезка из семейства I . Пусть a число циклов, содержащих ровно один отрезок из семейства I , тогда a n + 1. Оценим общее число циклов:

3n + 3 - a 3n + 3 + a = 2n + 2. 2 2 Перебрав несколько вариантов получим, что при n 3 число циклов не превосходит 2n + 1. a+
ном незамкнутого многообразия M 3 , если выполнены следующие три условия. (а) Комплекс P вложен в многообразие M 3 и гомеоморфны пространства:

Определение. Двумерный клеточный комплекс P называется специальным спай-

M 3 \ P M 3 Ч [0, 1),
(б) Для каждой точки из комплекса P существует ее окрестность в комплексе P , гомеоморфная конусу или над окружностью, или над окружностью с диаметром, или над окружностью с 3 радиусами, см. рис. 4. Точки третьего типа назовем вершинами полиэдра P . Точки второго и третьего типов назовем особым графом полиэдра P . (в) Комплекс P без особого графа гомеоморфен несвязному объединению дисков. Особый граф без своих вершин гомеоморфен несвязному объединению интервалов.
2 многообразия M 3 состоит из N сфер с gi ручками, то есть M 3 N Sgi . Тогда i=1 число вершин n в специальном спайне M 3 (если оно не равно 1 или 2) оценивается снизу: N

Следствие леммы 1. Пусть край компактного ориентируемого незамкнутого

n

|
i=1

(1 - gi ) - 1|.

Доказательство состоит из применения леммы 1 и подсчета эйлеровой характеристики (M ). 3 Рассмотрим полные сферы с gi ручками Sgi (полнотория). Так как сфера S 3 допускает разбиение Хегора любого рода, то
3 (Sgi ) = 2 (Sgi ) = 1 - gi . 2

39


3 Заклеим границу многообразия M 3 полными сферами с gi ручками Sgi , получится замкнутое многообразие N

M

3 i=1

3 S gi .

Эйлерова характеристика трехмерного замкнутого многообразия равна нулю, поэтому
N

(M ) =
i=1

3

(1 - gi ).

Специальный спайн M 3 гомотопически эквивалентен M 3 , а значит у них одинаковые эйлеровы характеристики, то есть

(M 3 ) = n - 2n + c,
где c это количество двумерных граней у спайна, оно же количество циклов и по лемме 1 верны неравенства

1

c

2n + 1 поэтому 1 - n

(M 3 )

n+1

Замечание. Для специальных спайнов с одной двумерной клеткой (например, получаемых в следующей лемме 2) количество граней c = 1, поэтому оценка в следствии леммы 1 для таких спайнов точна. 3.2 Серия специальных спайнов с одной двумерной клеткой. Для четного n 2 построим на плоскости R2 граф Gn из n вершин степени 4,

см. рис. 5. Рассмотрим n + 2 окружностей единичного радиуса с центрами в точках 2 (2k , 0), где k = 1, 2, . . . , n + 2 и n - 1 окружность радиуса 1 с центрами в точках 2 2 2 (2k + 4, 3 ), где k = 1, 2, . . . , n - 1. 2 2

4 существует как минимум 3 ћ (6 2)n-4 ориентируемых спайнов с особым графом Gn и с одной двумерной клеткой. Докажем лемму 2 индукцией по n. Будем рассматривать не сами спайны, а окрестности их особого графа Gn , т.е. проколем двумерную клетку. На рис. 6 изображена окрестность G2 . Для G2 возьмем полученную граничную окружность и ее три отрезка, проходящих вдоль дуги (5, 0) (6, -1) (7, 0). Перейдем к n = 4, то есть добавим к G2 еще 2 окружности. Продолжим эти три отрезка граничной S 1 вдоль добавленных окружностей: на каждую из них один продолженный отрезок намотается 2 раза, и еще один намотается 1 раз, см. рис. 7. На каждую добавленную окружность окрестность графа продолжается 6 способами (с сохранением ориентируемости). Выбор трех отрезков неоднозначен (их можно переставить между собой 6 способами, и дугу (5, 0) (6, -1) (7, 0) можно перепутать с дугой (5, 0) (6, 1)), поэтому для n = 4 найдено 6ћ6 = 3 спайна. Полученные спайны не гомеоморфны 6ћ2 друг другу, так как если у гомеоморфных спайнов выделенные отрезки совпадут, то дальше все продолжения совпадут.

Лемма 2. Для любого четного n

40


Перейдем теперь от n к n + 2: добавление еще двух окружностей дает 6 ћ 6 вариантов продолжения окрестности бывшего особого графа на новый особый граф (аналогично переходу G2 G4 ). Однако на прошлом шаге n - 2 n добавляемые окружности были одинаковы, а теперь на одной из них висят еще 2 окружности, значит на шаге n - 2 n получаем удвоение числа вариантов от того, на какую из 2 несимметричных окружностей будет начато продолжение окрестности особого графа.

Определение. Сложность трехмерного незамкнутого ориентируемого гиперболического многообразия равна минимально возможному числу вершин его специального спайна. Следствие леммы 2 и теорем из [F M P 03]. Для любого четного числа n 4 существует как минимум 3 ћ (6 2)n-4 компактных незамкнутых ориентируемых гиперболических многообразий сложности n с геодезической границей. 3.3 Специальные спайны с одной двумерной клеткой аналоги примеров Адамса. Лемма 3. Рассмотрим регулярные окрестности особых графов G специальных

спайнов, имеющих одну двумерную клетку. Все эти окрестности ретрагируются на 1 свою граничную окружность S0 (то есть на границу диска, выброшенного из двумерной клетки спайна). Используем теорию препятствий: если граница диска отображается на окруж1 ность S0 со степенью 0, то отображение границы продолжается до отображения всего 1 диска на окружность S0 . Сжимая регулярную окрестность P особого графа G, получим отображение гра1 ницы окрестности на особый граф f : S0 G. Выберем какую-нибудь вершину графа G, тогда на хотя бы одно из 4 выходящих 1 из нее ребер (пусть на ребро e) граничная окружность S0 отображается со степенью +1 или -1, см. рис. 8. Теперь весь особый граф без ребра e (т.е. G \ e) отображаем 1 в произвольную фиксированную точку x0 S0 на граничной окружности, а ребро e отображаем на граничную окружность со степенью +1 или -1 соответственно (отоб1 ражению граничной окружности на это ребро e). А саму окружность S0 как часть одномерного остова регулярной поверхности отобразим на граничную окружность 1 S0 тождественно. Соединим точку x0 с точкой (неважно какой) из остатка особого графа G \ e путем m (отрезком, непересекающим особый граф G) и отобразим путь m в точку x0 , см. рис. 9. Представим регулярную окрестность P в виде клеточного комплекса с одномерным остовом
1 G S0 m.

Тогда граница двумерной клетки регулярной окрестности P
1 (P \ (G S0 m)) 1 отображается со степенью 0 на граничную окружность S0 . Поэтому отображение границы можно продолжить до отображения всей регулярной окрестности P, сохра-

41


нив тождественное отображение граничной окружности на себя. То есть получилась ретракция регулярной поверхности на граничную окружность. Адамс рассматривал тройной лист Мебиуса, соединенный ленточкой с обычным листом и ретрагировал ее на границу.

42


4. Пример прямой без вещественных точек, лежащей в пересечении трех комплексных квадрик.
4.1 Возникновение задачи из теории интегрируемых систем.
В теории динамических систем очень важным оказался тот факт, что уравнения, возникающие из движения трехмерного твердого тела (например, с закрепленной точкой, в несжимаемой жидкости, связки двух тел, то есть тела с встроенным гироскопом) могут быть записаны в гамильтоновом виде xi = {xi , H } на соответствую щей алгебре Ли (обычно e(3) или so(4)) с подходящим гамильтонианом H (обычно квадратичной функцией от координат на алгебрe). Для основных случаев интегрируемости, кроме четырехмерного твердого тела, (и частично, случая Стеклова) в работах А.Т. Фоменко, А.А. Ошемкова, А.В. Болсинова, Х. Цишанга, явно вычислены метки и найдены изоэнергетические поверхности (трехмерные многообразия совместного уровня двух интегралов - инвариантов алгебры Ли и гамильтониана, задающего динамическую систему.) Есть примеры изоэнергетических поверхностей для последнего оставшегося случая, но нет доказательства, что других поверхностей не бывает. В случае четырехмерного твердого тела на алгебре so(4), реализованной как кососимметрические матрицы с обычным коммутатором и полученной по нему скобкой, заданы 2 интеграла
2 2 2 2 2 2 f1 = X1 + X2 + X3 + X4 + X5 + X6

и

f2 = X1 X4 + X2 X5 + X3 X6 .

Совместная поверхность уровня f1 = d1 , f2 = d2 является орбитой присоединенного действия группы Ли S O(4), при d1 > 2|d2 | эта орбита неособа, скобка на ней задает симплектическую структуру, и сама орбита диффеоморфна многообразию S 2 Ч S 2 . 2 2 2 2 2 2 Рассмотрим гамильтониан вида f3 = c1 X1 + c2 X2 + c3 X3 + c4 X4 + c5 X5 + c6 X6 для вещественных чисел c1 , . . . , c6 . Известно, что если параметры удовлетворяют соотношению

c1 c4 (c2 + c5 - c3 - c6 ) + c2 c5 (c3 + c6 - c1 - c4 ) + c3 c6 (c1 + c4 - c2 - c5 ) = 0,
то гамильтонова система интегрируема по Лиувиллю (то есть существует еще один интеграл, постоянный вдоль траекторий векторного поля sg radH ). Поэтому разумно искать трехмерное многообразие уровня и при других значениях параметров, где ничего большего узнать нельзя. А.Б. Жеглов предложил получить ограничения на топологию возможных изоэнергетических поверхностей, используя теорему Коллара [K ol], Theorem 1.1, в ее сильной формулировке.

4.2 Условия применимости теорем алгебраической геометрии.
Для этого исходное вещественное многообразие представляется как вещественная часть от пересечения трех квадрик Q3 = Q1 Q2 Q3 CP6 , находятся условия на паc раметры ci , dj , при которых пересечение будет алгебраическим подмногообразием CP6 (и, как следствие, полным пересечением), по формуле для размерности множества одномерных линейных подпространств (см. [ХоП]) получаем, что в Q3 есть c однопараметрическое семейство прямых (комплексных). Поэтому можно определить проекцию из Q3 на CP2 следующим образом: фиксируем прямую m, лежащую в Q3 , c c 43


рассматриваем CP2 как множество квадрик, содержащих Q3 , и точке x ставим в соc ответствие квадрику, содержащую плоскость (x, m). Это отображение не определено ~ на самой прямой m и на прямых, ее пересекающих. Поэтому рассмотрим раздутие Q3 c ~ 3 CP2 ) теорему Коллара, получим, и применим к нему (точнее к отображению Qc ~ что вещественные точки Q3 есть одно из следующих многообразий: RP3 , S 3 , S 2 Ч S 1 , c их связные суммы, многообразия Зейферта с не более 6 особыми слоями, линзы с p, q 6. Однако для нахождения изоэнергетической поверхности нужно, чтобы ~ вещественные точки у многообразий Q3 и Q3 совпали, для этого достаточно, чтоc c бы раздутие не касалось вещественных точек, то есть прямая проекции и все прямые, ее пересекающие, не имели бы вещественных точек. В данном параграфе найдены условия на параметры квадрик, при которых поверхность уровня f1 = d1 , f2 = d2 , f3 = d3 невырождена в C6 (теорема 4 и замечание к ней), явно найдена прямая (определяемая вещественным параметром и комплексным (для почти всех исходных многообразий Q3 ) параметром ч), вдоль которой можно R проецировать и вдоль которой раздувается многообразие (на ней нет вещественных точек). В дальнейшем для применения теоремы Коллара надо проверить, что ни одна прямая, пересекающая найденную и лежащая целиком в алгебраическом многобразии Q3 CP6 , не проходит через вещественное многообразие Q3 R6 . С помощью c R ~ найденной прямой можно будет построить раздутие Q3 многообразия Q3 и усилить c c оценку теоремы Коллара.

Теорема 4. Множество уровня трех вещественных функций Q3 = {f1 = R d1 , f2 = d2 , f3 = d3 } R6 является трехмерным вещественным многообразием
тогда и только тогда, когда (а) d1 > 2|d2 | и (б) не существует такого вещественного числа b, которое удовлетворяло бы всем трем уравнениям:

4.3 Невырожденность в R6 и в C6 .

1) (c1 - a)(c4 - a) = b2 , 2) (c2 - a)(c5 - a) = b2 , 3) (c3 - a)(c6 - a) = b2 ,
и хотя бы одному неравенству:

1) 2) 3)

c1 - a bd2 c2 - a bd2 c3 - a bd2

1 + ( c1 d1 1 + ( c2 d1 1 + ( c3 d1

-a 2 ) b -a 2 ) b -a 2 ) b

, , ,

где a = d3 -2bd2 . d1 Эти условия получаются как условия, при которых матрица Якоби производных функций f1 , f2 , f3 по переменным X1 , . . . , X6 размера 3 Ч 6 невырождена во всех точках множества Q3 . R Обратно, если условие (а) не выполняется, то в матрице Якоби первые 2 строчки зависимы или множество Q3 пустое. R 44


Если условие (б) не выполняется, то ранг матрицы Якоби равен 2 в точке с координатами x1 , . . . , x6 , где

c4 - a c4 - a )x1 , x5 = ( )x2 , b b а числа x1 , x2 , x3 являются решением системы: x4 = ( d1 = x d2 = x d3 = x
2 1 2 1 2 1

x6 = (

c4 - a )x3 , b

1+

(c1 - a)2 (c2 + x2 1 + 2 2 b (c1 - a) (c2 - a) + x2 + 2 b b (c1 - a)2 c1 + c4 + x2 c2 + 2 b2

- a)2 (c3 - a)2 + x2 1 + , 3 b2 b2 (c3 - a) x2 , 3 b (c2 - a)2 (c3 - a)2 c5 + x2 c 3 + c 6 3 b2 b2

.

Множество уровня трех комплексных функций Q3 = {f1 = d1 , f2 = d2 , f3 = C d3 } C6 является трехмерным комплексным многообразием тогда и только тогда, когда (а) d1 = 2|d2 | и (б) не существует такого комплексного числа b, которое удовлетворяло бы всем трем уравнениям:

Замечание. Невырожденность в C6 аналогична:

1) (c1 - a)(c4 - a) = b2 , 2) (c2 - a)(c5 - a) = b2 , 3) (c3 - a)(c6 - a) = b2 ,
карт, в каждой из которых условия невырожденности будут аналогичны условиям невырожденности в C6 .

Замечание. Невырожденность в CP6 получается расмотрением 7 аффинных

4.4 Прямая без вещественных точек.
На многообразии Q3 будем искать прямую с дополнительными условиями и найc дем ее для почти всех значений параметров. Прямая задается в виде

xi = ai + tbi

для

i = 1, 2, . . . 6,

где коэффициенты ai , bi это комплексные числа, а t это комплексная переменная. Наложим условия на коэффициенты прямой:

a4 = a1 ,

a5 = a2 ,

a6 = a

3

и

b4 = чb1 ,

b5 = чb2 ,

b6 = чb3 .

После подстановки параметрического задания прямой в три уравнения, задающие многообразие Q3 , получим девять уравнений (при t2 , t и свободном члене для c каждого из трех уравнения fj = dj ), но из-за дополнительной симметрии, возникающей из наложенных условий на коэффициенты прямой, независимых уравнений будет семь, переменных же восемь: a1 , a2 , a3 , b1 , b2 , b3 , , ч; поэтому положим число 1 равным корню уравнения x + x = d1 , и число ч равным корню уравнения d2

45


c2 - c3 + ч2 (c5 - c6 )

c3 - c1 + ч2 (c6 - c4 )(d3 -

+ (c1 - c3 + 2 (c4 - c6 ))( + + = 0.

d2 (c2 + 2 c5 ) - d3 )(c1 - c2 + ч(c4 - c5 ))+ d2 c2 - c3 + ч2 (c5 - c6 ) c1 - c2 + ч2 (c4 - c5 )( (c2 + 2 c5 ) - d3 )(c1 - c3 + ч(c4 - c6 ))+ d2 c3 - c1 + ч2 (c6 - c4 ) c1 - c2 + ч2 (c4 - c5 )(d3 - (c1 + 2 c4 ))(c2 - c3 + ч(c5 - c6 )) =

d2 (c1 + 2 c4 ))(c2 - c3 + 2 (c5 - c6 ))+

Теперь находятся числа

b1 = b2 = b3 =
и находятся числа a1 ,

c2 - c3 + ч2 (c5 - c6 ), c3 - c1 + ч2 (c6 - c4 ), c1 - c2 + ч2 (c4 - c5 ),

a2 ,

a3 по громоздким формулам.

пара условий c1 = c2 и c4 = c5 , не выполняется одновременно пара условий c1 = c3 и c4 = c6 , у уравнения на ч есть корень, отличный от и от -, не все числа a1 , a2 , a3 вещественны. Тогда для любого комплексного числа t шесть чисел aj + tbj не могут быть одновременно вещественными. Предположим противное, то есть что числа ai + tbi и ai + tчbi одновременно вещественны, тогда три числа (ai + tbi ) вещественны. Вычтем вторые числа из третьих (для всех i = 1, 2, 3), получим вещественность чисел t( - ч)bi . Деля полученные числа одно на другое (они не равны нулю по сделанным предположениям), получим b2 вещественность чисел b1 и b3 . b1 Числа bi удовлетворяют уравнению b2 + b2 + b2 = 0. Из вещественности чисел b2 1 2 3 b1 и b3 следует, что b1 = b2 = b3 = 0. Однако подстановка b1 = b2 = b3 = 0 в уравнение b1 на ч даст уравнение

Лемма. Предположим, что ( d2 (c2 + 2 c5 ) - d3 ) = 0, не выполняется одновременно

d2 (c2 + 2 c5 ) - d3 )(c1 - c2 + ч(c4 - c5 )) = 0 Каждый из трех множителей не может быть равен нулю по сделанным предположениям. (c1 - c3 + 2 (c4 - c6 ))(
ет вещественно одномерное множество вещественных точек, сквозь которые проходят прямые m Q3 . Множество же самих прямых вещественно двумерно, однако пряc мые могут густо пересекаться, поэтому применение теоремы Коллара нетривиально, и будет осуществлено с помощью найденной явно прямой.

Итог: Можно заметить, что для почти всех значений параметров на Q3 существуc

46


5. Алгоритмы пересечения поверхностей прямой
Общая постановка задачи.
Найти по возможности явные алгоритмы нахождения всех точек пересечения двумерных поверхностей компьютерной геометрии (см. список ниже) с пучками прямых следующих типов: равномерным, цилиндрическим, сферическим.

Применение задачи для построения поверхностных нерегулярных сеток.
Для численного расчета физических процессов, происходящих в теле сложной конструкции, тело представляется ограниченным набором поверхностей различных типов. Далее строится подходящая (для физ. процесса) нерегулярная сетка на поверхности тела и продолжается внутрь тела (по заданному набору ограничивающих поверхностей). Построение сетки на поверхности тела лаборатория 0805 ИТМФ ВНИИЭФ предлагает получить, построив точки пересечения всех ограничивающих тело поверхностей с пучками прямых (равномерным, цилиндрическим, сферическим). Компьютерные программы ограничивают тело следующими поверхностями. 1) Поверхность вращения. 2) Линейчатая поверхность. 3) Поверхность выдавливания. 4) Поверхность скругления. 5) Бикубическая сплайновая поверхность. 6) NURBS поверхность. 7) Поверхность Кунса. 8) Цилиндрическая бикубическая поверхность. В качестве образующих кривых для поверхностей берутся кубические сплайны, дуги окружностей и эллипсов, отрезки прямых. В настоящей работе для трех поверхностей поверхности вращения, линейчатой поверхности и поверхности выдавливания приведены явные алгоритмы, находящие все точки пересечения (по модулю решения одного уравнения одного неизвестного для каждой прямой и некоторых типов поверхностей и проверке найденных решений).

- сти - (u, v ) и прямой (t) равносильно векторному уравнению s r (u, v ) = - (t) - s r

Теоретическое обоснование алгоритмов. В трехмерном пространстве R3 пересечение параметрически заданных поверхно(1)

на три скалярных параметра u, v , t. В общем случае точки пересечения образуют конечное множество. Поверхности строятся по образующей кривой - (u) (некоторые c - (u), - (u)). Секущая прямая - (t) парамет строятся по двум образующим кривым c1 c2 r ризуется

- (t) = - + t- . r k n - с произвольной принадлежащей ей точкой k = (k1 , k2 , k3 ) и направляющим век тором - = (n1 , n2 , n3 ). n
47


Для каждой из трех рассмотренных поверхностей, векторное уравнение (1) сведено к уравнениям второй степени на координатные функции x(u), y (u), z (u) обра зующих кривых - (u) (при этом координатные функции x(u), y (u), z (u) параметра u c образующих кривых рассматриваются как независимые переменные x, y , z ). Под эквивалентностью уравнений в предложениях 1, 2 и 3 имеется в виду совпадение множества решений u скалярного уравнения и множества первых компонент решений (u, v , t) векторного уравнения (1). Рассмотрены все случаи взаимного расположения прямой и поверхности, в том числе вырожденные. В каждом случае получено свое скалярное уравнение переменной u и приведен алгоритм нахождения двух других компонент v , t векторного уравнения (1). В постановке задачи требуется найти все решения (u, v , t) векторного уравнения (1), удовлетворяющие ограничениям

u

min

u

u

max

и

v

min

v

v

max

.

Поэтому алгоритмы включают в себя проверку принадлежности найденных решений u, v отрезкам [umin , umax ], [vmin , vmax ] и в некоторых случаях проверку того, что найденная тройка чисел (u, v , t) является решением векторного уравнения (1). Предложение 1. Векторное уравнение пересечения поверхности вращения и секущей прямой

- - x(u)cos(v )- + x(u)sin(v )- + z (u) = k + t- e1 e2 e3 n
эквивалентно (в общем случае) уравнению второй степени (уравнению гиперболы):

x2 (u) -

n2 + n 1 n2 3

2 2

2 2 (z (u) - )2 = k1 + k2 -

(n1 k1 + n2 k2 )2 , n2 + n2 1 2

где константа = k3 - и секущей прямой

Предложение 2. Векторное уравнение пересечения линейчатой поверхности
- v - (u) + (1 - v )- (u) = k + t- c1 c2 n
эквивалентно (в общем случае) равенству нулю определителя - (u) - - c1 k - (u) - - = 0. det c2 k - n

n3 (n1 k1 +n2 k2 ) n2 +n2 2 1

.

ния и секущей прямой

Предложение 3. Векторное уравнение пересечения поверхности выдавлива - x(u)- + y (u)- + v - = k + t- e1 e2 e3 n
эквивалентно (в общем случае) линейному уравнению

n2 (x(u) - k1 ) = n1 (y (u) - k2 ).

48


Подстановка явной (выдаваемой компьютерной программой) зависимости координатных функций x(u), y (u), z (u) от параметра u в полученное уравнение дает уравнение одной переменной u. (Для используемых сейчас программ это уравнение получается степени не выше 6). Специальный алгоритм быстрого (порядка const ћ ln( 1 ), где это точность вычислений) решения уравнения 6 степени выдает значения параметра u всех точек пересечения (для каждого сегмента образующей кривой).

5.1 Поверхность вращения.
секущей прямой

Предложение 1. Векторное уравнение пересечения поверхности вращения и
- - x(u)cos(v )- + x(u)sin(v )- + z (u) = k + t- e1 e2 e3 n
эквивалентно (в общем случае) уравнению второй степени:

(1)

x2 (u) -

n2 + n 1 n2 3

2 2

2 2 (z (u) - )2 = k1 + k2 -

(n1 k1 + n2 k2 )2 , n2 + n2 1 2

(2)

где константа = k3 -

на первый и третий координатные вектора - , - задана образующая кривая e1 e3 - (u) = x(u)- + z (u)- , c e1 e3
где u [u
min

Параметрическое задание поверхности вращения. В плоскости, натянутой
,u
max

n3 (n1 k1 +n2 k2 ) n2 +n2 1 2

.

].

(3)

Поверхность вращения получается вращением образующей кривой вокруг оси третьего координатного вектора - . Точки поверхности вращения параметризуетe3 ся двумя параметрами, параметром u образующей кривой и углом поворота v [vmin , vmax ]. Параметрическое уравнение поверхности вращения имеет вид

- (u, v ) = x(u)cos(v )- + x(u)sin(v )- + z (u). - s e1 e2 e3

(4)

Доказательство предложения 1.

Перепишем уравнение (1) в координатах:

x(u)cos(v ) = n1 t + k1 x(u)sin(v ) = n2 t + k2 z (u) = n3 t + k3
Рассмотрим три случая:

(5)

Случай (а), (общий), верно n3 = 0 и n2 + n2 = 0. 2 1
Из третьего уравнения системы (5) выразим t = нения системы (5) в квадрат и сложим их:
z -k3 n3

. Возведем первые два урав(6)

2 2 x2 = (n2 + n2 )t2 + 2(n1 k1 + n2 k2 )t + k1 + k2 2 1

В правой части равенства (6) выделим полный квадрат относительно t :

x2 = (n2 + n2 )(t + 1 2

(n1 k1 + n2 k2 ) 2 (n1 k1 + n2 k2 )2 2 2 ) + k1 + k2 - (n2 + n2 ) (n2 + n2 ) 1 2 1 2
49

(7)


Учитывая t = (7) выражение

z -k n3

3

, преобразуем возводимое в квадрат в правой части равенства
k2 )

1 k1 2 z - k3 + n3 (nn2 ++n) (n1 k1 + n2 k2 ) ( 1 n2 2 t+ = (n2 + n2 ) n3 1 2

=

z- n3

(8)

Перенося в равенстве (7) полный квадрат в левую часть и используя равенство (8), получим искомое уравнение:

x2 -

n2 + n 1 n2 3

2 2

2 2 (z - )2 = k1 + k2 -

(n1 k1 + n2 k2 )2 , (n2 + n2 ) 1 2

(2)

1 k1 где константа = k3 - n3 (nn2 ++n2 k2 ) . 2 1 n2 Подставим в выведенное уравнение (2) явную зависимость координатных функций x(u) и z (u) от параметра u (например, если образующая кривая это кубический сплайн, то функции x(u) и z (u) будут многочленами третьей степени). Получим уравнение на u :

x(u)2 -

n2 + n2 1 2 n2 3

2 2 (z (u) - )2 = k1 + k2 -

(n1 k1 + n2 k2 )2 (n2 + n2 ) 1 2

(2 )

Если образующая кривая это кубический сплайн, то уравнение (2 ) будет шестой степени, если дуга эллипса, то четвертой степени. Обозначим за u1 , . . . , uk те корни уравнения (2 ), которые принадлежат отрезку [umin , umax ]. Найдем значения параметра t в точках пересечения по третьему уравнению системы (5): z (ui ) - k3 ti = , i = 1, . . . , k . n3 Найдем значения параметра v в точках пересечения из второго уравнения системы (5):

v

i,1

= arcsin

n2 ti + k2 x(ui )

,

v

i,2

= - arcsin
i,2

n2 ti + k x(ui )

2

,

i = 1, . . . , k .

Проверим найденные значения vi,1 , v системы (5):

на совпадение знаков в первом уравнении

x(ui )cos(vi,j ) = n1 ti + k1 ,
Проверим найденные значения vi,1 , v [vmin , vmax ] [- , 32 ]. 2
i,2

i = 1, . . . , k ,

j = 1, 2.

на принадлежность заданному отрезку

Случай (б), верно n3 = 0 и n1 = n2 = 0.
Это случай пересечения прямой, паралельной оси вращения поверхности. Первые два уравнения системы (5) принимают вид

xcos(v ) = k1 ,

xsin(v ) = k2 .

2 2 Возводя их в квадрат и складывая, получим x2 = k1 + k2 .

50


Подставим в полученное уравнение пары прямых x = + мость x(u), получим уравнение (точнее пару уравнений):

2 2 k1 + k2 явную зависи-

x(u) = +

2 2 k1 + k2 .

(9)

Если образующая кривая это кубический сплайн, то уравнения (9) будет третьей степени, если дуга эллипса, то второй степени. Обозначим за u1 , . . . , uk те корни уравнений (9), которые принадлежат отрезку [umin , umax ]. Найдем значения параметра v в точках пересечения из второго уравнения системы (5):

v

i,1

= arcsin

k2 x(ui )

,

v

i,2

= - arcsin
i,2

k2 x(ui )

,

i = 1, . . . , k .

Проверим найденные значения vi,1 , v системы (5): x(ui )cos(vi,j ) = k1 ,
3 , 22

на совпадение знаков в первом уравнении

i = 1, . . . , k ,

j = 1, 2.

Проверим значения vi,1 , vi,2 на принадлежность заданному отрезку [vmin , vmax ] [- ]. Найдем значения параметра t в точках пересечения по третьему уравнению системы (5): z (ui ) - k3 ti = , i = 1, . . . , k . n3

Случай (в), верно n3 = 0.
Это случай, когда секущая прямая лежит в плоскости, перпендикулярной оси вращения поверхности. Третье уравнение системы (5) имеет вид z (u) = k3 . Если образующая кривая это кубический сплайн, то уравнение z (u) = k3 будет третьей степени, если дуга эллипса, то второй степени. Обозначим за u1 , . . . , uk те корни уравнения z (u) = k3 , которые принадлежат отрезку [umin , umax ]. Подставив корни ui в первые два уравнения системы (5), получим (для каждого i = 1, . . . , k ) два уравнения на две неизвестных t, v :

x(ui )cos(v ) = n1 t + k1 ,

x(ui )sin(v ) = n2 t + k

2

(10)

Возводя оба уравнения из (10) в квадрат и складывая, получим квадратное уравнение (для каждого i = 1, . . . , k ) на t :
2 2 x2 (ui ) = (n2 + n2 )t2 + 2(n1 k1 + n2 k2 )t + k1 + k2 2 1

Обозначим его корни за ti,1 и ti,2 . Найдем значения параметра v в точках пересечения из второго уравнения системы (5):

vi,j,1 = arcsin

n2 ti,j + k x(ui )

2

,

v

i,j,2

= - arcsin

n2 ti,j + k2 x(ui )

,

51


где i = 1, . . . , k , j = 1, 2. Проверим найденные значения v

i,j,1

,v

i,j,2

,t

i,j

на обоих уравнениях (10):
i,j,h

x(ui )cos(v

i,j,h

) = n1 t

i,j

+ k1 ,

x(ui )sin(v

) = n2 t

i,j

+ k2 ,
min

где i = 1, . . . , k , j = 1, 2, и h = 1, 2. Проверим значения vi,j,h на принадлежность заданному отрезку [v 3 [- 2 , 2 ].

,v

max

]

5.2 Линейчатая поверхность.
и секущей прямой

Предложение 2. Векторное уравнение пересечения линейчатой поверхности
- v - (u) + (1 - v )- (u) = k + t- c1 c2 n
эквивалентно (в общем случае) равенству нулю определителя - (u) - - c1 k det - (u) - - = 0. c2 k - n

(1)

(2)

Параметрическое задание линейчатой поверхности. В трехмерном пространстве R3 заданы две образующие кривые
- (u), c1 - (u), c2
где u [u
min

,u

max

].

(3)

Линейчатая поверхность получается соединением отрезками соответствующих точек образующих кривых и параметризуется двумя параметрами (u и v ):

- (u, v ) = v - (u) + (1 - v )- (u), s c1 c2

где v [0, 1].

(4)

Доказательство предложения 2.

Векторное уравнение (1) равносильно уравнению

-- k - c2 (u) = v (- (u) - - (u)) - t- . c1 c2 n

(5)

на три скалярных параметра u, v , t. Зафиксируем значение переменной u и найдем точки пересечения секущей прямой с отрезком линейчатой поверхности, задаваемым фиксированным u. Рассмотрим 6 случаев паралелльности или равенства нулю векторов

-- k - c2 (u),

(u) - - (u), - c1 c2

. - n

(6)

Случай (а) (общий), никакая пара векторов из (6) не паралелльна и никакой вектор из (6) не равен нулю.
Этот случай возможен, когда секущая прямая пересекает линейчатую поверхность во внутренней точке. 52


- Уравнение (5) определяет представление вектора k - - (u) линейной комбинаc2 - (u) - - (u) и - , поэтому из уравнения (5) следует, что все вектора цией векторов c1 c2 n из набора (6) лежат в одной плоскости, то есть определитель матрицы, составленной из координат векторов набора (6), равен нулю: - - k - c2 (u) det - (u) - - (u) = 0. (7) c1 c2 - n
Заменяя вторую строку равенства (7) на разность между второй и первой, получаем уравнение (2). Обратно, уравнение (2) влечет равенство (7), из которого следует, что три вектора из набора (6) лежат в одной плоскости. Тогда равенство (5) будет выполнено для каких-то значений переменных v , t, то есть секущая прямая пересекает прямую, содержащую отрезок линейчатой поверхности, определяемый фиксированным значением переменной u. Для того, чтобы найти значения переменных v , t, умножим уравнение (5) скаляр - но на вектор - (u) - (u) и на вектор - , получим систему двух линейных уравнений c1 c2 n на две неизвестные v , t :

-- k - c2 (u) ћ -- k - c2 (u) ћ

- ((u) - - (u)) = v - (u) - - (u) c1 c2 c1 c2 - = v (- (u) - - (u)) ћ - t - - n c1 c2 n n
2

2

- - t- ћ (- (u) - (u)) n c1 c2

(8)

У системы (8) решение существует и единственно, так как (в общем случае (а)) вектора - (u) - - (u) и - линейно независимы. c1 c2 n - Случай (б), верно равенство (u) = - (u). c1 c2 В этом случае образующие кривые пересекаются. Для нахождения точки пере сечения необходимо и достаточно проверить, что точка - (u) = - (u) принадлежит c1 c2 - -. секущей прямой k + t n - Случай (в), вектор k - - (u) равен нулю или паралеллен вектору - . c2 n - (u) образующей кривой. В этом случае секущая прямая проходит через точку c2 - Точка пересечения находится сразу это точка (u). Параметр v этой точки как c точки поверхности равен нулю: v = 0.
2

В этом случае секущая прямая проходит через отрезок линейчатой поверхности, определяемый фиксированным значением переменной u для всех возможных значений переменной v [0, 1]. - Случай (д), вектора k - - (u) и - (u) - - (u) паралелльны. c2 c1 c2 - В этом случае точка k лежит на прямой, содержащей отрезок линейчатой поверхности с фиксированным u. Значение переменной v определяется из равенства

Случай (г), все вектора из (6) паралелльны и отличны от нуля.

-- - k - c2 (u) = v ((u) - - (u)). c1 c2 - - - Случай (е), вектора и - (u) - (u) паралелльны. Вектора - и k - - (u) n c1 c2 n c2 не паралелльны.
53


В этом случае секущая прямая паралелльна и не пересекает прямую, содержащую отрезок линейчатой поверхности с фиксированным u. Соберем теперь все случаи вместе. Чтобы найти все точки пересечения линейчатой поверхности и прямой, нужно:

ћ Найти все решения ui (индекс i нумерует решения) уравнения (2), принадлежащие отрезку [umin , umax ]. ћ Для каждого найденного решения ui рассмотреть соответствующий ему случай из случаев (а)-(е). В случаях (в), (г) можно сразу указать ответ; в случае (е) точек пересечения нет. В случае (б) нужна проверка принадлежности точки (поверхности) секущей прямой. ћ В случаях (а), (д) находится значение vi переменной v и осуществляется проверка vi [0, 1].

5.3 Поверхность выдавливания.
ния с секущей прямой

Предложение 3. Векторное уравнение пересечения поверхности выдавлива - x(u)- + y (u)- + v - = k + t- e1 e2 e3 n
эквивалентно (в общем случае) линейному уравнению

(1)

n2 (x(u) - k1 ) = n1 (y (u) - k2 ).

(2)

- В плоскости, натянутой на первые два базисных вектора - , задана образуюe1 e2 щая кривая - (u) = x(u)- + y (u)- , c e1 e2
где u [u
min

Параметрическое задание поверхности выдавливания.

,u

max

].

(3)

Поверхность выдавливания получается паралелльным переносом образующей кри вой по направлению третьего базисного вектора - . Точка на поверхности выдавлиe3 вания параметризуется параметром u образующей кривой и параметром v дальностью переноса, то есть

- (u, v ) = x(u)- + y (u)- + v . - s e1 e2 e3

(4)

Доказательство предложения 3. Случай (а) общий, n2 + n2 > 0. 2 1

Проекции уравнения (1) на оси векторов - и - имеют вид e1 e2 x(u) = k1 + tn1 y (u) = k2 + tn2
54


Исключая переменную t, получим уравнение (2). Решения уравнения (2) дают параметры u точек пересечения. Параметр v нахо-- дится из проекций уравнения (1) на оси и : e1 e3

v = k3 + n

3

x ( u) - k n1

1

В этом случае секущая прямая паралельна поверхности выдавливания. Если точка k1 - + k2 - принадлежит образующей кривой - (u), то секущая пряe1 e2 c мая пересекает поверхность по отрезку, если точка не принадлежит образующей кривой, то прямая не пересекает поверхность.

Случай (б), n1 = n2 = 0.

55


[Арн08] Арнольд В.И., На сколько частей делят плоскость n прямых? // Матем. просвещение, серия 3, 12, (2008) 95104. [Gru72] Grunbaum B., Arrangements and spreads// CBMS Regional Conference Series Е in Mathematics, No. 10. AMS Providence, R.I., 1972. [Mar90] Martinov N.J., On conjecture 2.4 of Grunbaum // Mathematics and Education in Mathematics (Proc. 19th Spring Conference of the Union of Bulgarian Mathematicians, Sunny Beach, April 1990). Bulgarian Academy of Science, Soa, 1990, pp. 112117. [Mar93] Martinov N., Classication of arrangements by the number of their cel ls // Discrete and Comput. Geometry, Vol. 9, 1 (1993), 39-46. Е [Mel41] Melchior E., U ber Vielseite der Projektiven Ebene // Deutsche Mathematik 5, (1941) 461-475. [Аки03] Акимов О.Е., Дискретная математика: логика, группы, графы // М.: Лаборатория Базовых Знаний, 2003 // пар. 4.1, стр. 337-339. [ГКФ81] Гильберт Д., Кон-Фоссен С., Наглядная геометрия // М. Наука 1981. [Зуе91] Зуев Ю.А., Комбинаторно-вероятностные и геометрические методы в пороговой логике // Дискретная математика 1991, т. 3, вып. 2, стр. 47-57. [Пой75] Пойа Д., Математика и правдоподобные рассуждения // М., Наука, 1975. [BMP05] Brass P., Mozer W., Pach J., Research Problems in Discrete Geometry // Springer 2005 // Chapter 7, Incidence and Arrangement Problems, pp. 289-324. [GPW05] Goodman J.E., Pach J., Welzl E. (editors), Combinatorial and Computational Geometry // Cambridge University Press, 2005 // 'Extremal Problems Related to the Sylvester-Gallai Theorem', written by Niranjan Nilakantan, pp. 479-494. [Sch50] Schlai L., Gesammelte mathematische Abhand lugen. Band 1 // Basel, Birkhauser Е Е Verlag, 1950. [BNR02] Ben-Tal A., Nemirovski A., Roos C., Robust solutions to uncertain quadratic and conic-quadratic problems // SIAM Journal on Optimization, 13, (2002), 535-560. [BN98] Ben-Tal A., Nemirovski A., Robust convex optimization // Math. Oper. Research, 23 4 (1998) 769-805. [Шир04] Ширяев А.Н., Вероятность-1 // М. МЦНМО, 2004. [FMP03] Frigerio R., Martelli B., Petronio C., Complexity and Heegard genus of an innite class of compact 3-manifolds// Pasic J. Math. (2003)// math.GT/0206156 v1 2002;

К параграфу про прямые:

Литература.

К параграфу про прямые, дополнительно:

К параграфу про многомерный куб:

К параграфу про спайны:

К параграфу про пересечение трех квадрик:

[Kol] Kollar J., Real Algebraic Threefolds 3. Conic bund les// arxiv AG/9802053 v1 [ХоП] Ходж, Пидо, Методы алгебраической геометрии//// гл. 13, пар. 6, теор. 1. [ГИН06] Голованов Н.Н., Ильютко Д.П., Носовский Г.В., Фоменко А.Т., Компьютерная геометрия // Москва, издательский центр "Академия 2006. 56

К параграфу про алгоритмы пересечения поверхностей прямой: