Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
алгоритм s4- решает вопрос о принадлежности точки q множеству Wi, то лист lh является принимающим. С другой стороны, по определению У из равенства Y(Wi)==h следует, что WtC\Dh непусто. Пусть q' — точка из Wi Г1 Dn, аналогично q" — точка из Wj П Dh> Поскольку Т — линейное дерево решений, то область в Еп, соответствующая Dn, образована пересечением полупространств, т. е. это выпуклая область. Значит, любая выпуклая комбинация точек из Рн принадлежит Dn (разд. 1.3.1). Рассмотрим теперь отрезок q'q" (рис. 1.9). Этот отрезок пересекает но крайней мере две компоненты W (он, безусловно, пересекает W, и Wj), и, поскольку эти компоненты разделены, он содержит по крайней мере одну точку q'" ф. W. Но так как область Dn выпукла, то весь отрезок q'q" принадлежит Dh, а, значит, и точка q'" принадлежит внутренности W. Получаем противоречие. В итоге Т должно иметь не менее р листов. Поскольку двоичное дерево наименьшей высоты с заданным числом листов сбалан-
') Область в.ходных данных, переводящих алгоритм в лист /,. — Прим.
1.4. Модели вычислений
49
сировано, то высота Т равна не менее чем log2р = log2#{W). Эти рассуждения приводят к следующей теореме.
Теорема 1.1 (Добкин — Липтон). Любое линейное дерево решений, алгоритм которого решает задачу о принадлежности W Е Еп, должно иметь высоту не меньше, чем log2#(№), где #(№) — число разделимых связных компонент W.
К сожалению, вышеизложенный метод ограничен алгоритмами линейного дерева вычислений, поскольку он опирается на свойство выпуклости области в Еп, связанной с листом этого дерева. Если же максимальная степень полиномов fv ^ 2, то это полезное свойство исчезает. Значит, нужны более глубокие представления.
Интуитивно ясно, что, когда используются полиномы более высоких степеней, тогда область, связанная с конкретным листом дерева решений, может состоять из нескольких разделимых компонент в W. Если удастся оценить число компонент, связанных с неким листом в терминах высоты этого листа в дереве, то, как мы вскоре увидим, нам удастся оценить высоту Т.
К счастью, ключ к решению этой трудной проблемы дала утонченная адаптация [Steele, Yao (1982); Ben-Or (1983)] одного классического результата из алгебраической геометрии, независимо полученного Милнором [Milnor (1964)] и Томом [Thorn (1965)]. Ниже излагается результат Милнора и Тома.
Пусть V — множество точек (так называемое алгебраическое многообразие) в m-мерном декартовом пространстве Ет, определенное полиномиальными уравнениями
Ы*......0 = 0; ...; gp{x{, *J = 0. (1.12)
Тогда, если степень каждого полинома gt (;'= 1, р) не превышает d, то число Ф(У) разделимых связных компонент1) V оценивается как:
#(K)<rf.(2rf- 1)т-\
К сожалению, множество V определено лишь посредством равенств (1.12), в то время как ограничения, связанные с путем в Т, состоят как из равенств, так и из неравенств. Эта трудность была блестяще преодолена Бен-Ором, который преобразовал ситуацию с деревом Т так, что она стала удовлетворять условию теоремы Милнора — Тома, как это будет сейчас показано.
') В действительности Милнор и Том доказали более сильный результат, что d(2d— l)m-' — это верхняя оценка суммы чисел Бетти для множества V, в то время как число ^= (V) связных компонент V — это только одно из таких чисел (число Бетти 0-го порядка).
гл. 1. Введение
Пусть U s Еп — множество точек, удовлетворяющих следующим ограничениям (здесь х = (хь х„)): qx (х) = 0, .... ?г(х) = 0,
р,(х)>0, р,{х)>0, (1.13)
P,+ i(x)>0.....pft(x)>0,
где q и р — полиномы, d = max{2, степень (<7,), степень (ру)}. Заметим, что имеется три типа ограничений: равенства, строгие неравенства и нестрогие неравенства. Пусть #(U) обозначает число связных компонент множества U.
Рис. 1.10. Построение UE по U; U ограничено сплошными линиями, 1/г — штриховыми.
Первый шаг преобразования состоит в замене строгих неравенств нестрогими. Поскольку #(?/) конечно (см. [Milnor (1968)]), положим #(?/) Д,/и поместим в каждую компоненту U по точке. Обозначив эти точки Vi, ..., vt, положим
е = min{pi(Vj): i—l, .... s; /=1.....t).
Поскольку каждая точка v,- е= U, то р,- (v/) > 0 (для i = 1, ... ..., s) и Е>0. Очевидно, что замкнутое множество точек UE, определяемое системой
<7l(x) = 0, qr(x) = 0,
Pi(x)>e.....ps(x)>e, (1.14)
Р.+ Л*)>0, ...,Ph(x)>0, содержится в U, #(?/e) ^ #(U), так как все V/ лежат в разных связных компонентах С/е (см. в качестве интуитивного примера рис. 1.10).
Второй шаг преобразования состоит во введении искусственных переменных у, для всех / = 1, ..., h (т. е. по одной для каждого из нестрогих неравенств), чтобы Еп рассматривалось как такое подпространство в Еп+Н, где
Г <7,(х) = 0, <7г(х) = 0,
| р,(х)-е-г/2 = 0, .... ps(x)-e-^ = 0, (1.15)
J P,+1W-.^+1 = 0.....рн(х)-у1 = 0.
1.4. Модели вычислений
51
Очевидно, что множество U* всех решений (1.15) представляет собой алгебраическое многообразие в Еп+Н, определенное полиномами степени, не превышающей d и удовлетворяющее условиям теоремы Милнора — Тома; следовательно, число Ф(1/*) связных компонент U* оценивается следующим образом:
