Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Однако Гильберт оценил важность нижних оценок. Работая с ограниченной моделью, он рассматривал только такие построения, которые можно выполнить с помощью односторонней линейки и шкалы — инструмента, используемого только для пометки отрезка фиксированной длины вдоль некоей линии. Не
1.1. Исторический обзор
13
все евклидовы построения выполнимы с помощью этого набора инструментов. Но для тех, что выполнимы, мы можем рассматривать координаты построенных точек как функцию F от заданных точек. Гильберт дал необходимое и достаточное условие вычислимости F с использованием ровно п операций извлечения квадратного корня — это одна из наиболее ранних теорем в алгебраической теории вычислительной сложности [Hilbert (1899)].
Есть основания думать, что многие из наших современных методов анализа алгоритмов были предвосхищены геометрами минувших столетии. В 1672 г. Джордж Мор показал, что любое построение, осуществимое с помощью линейки и циркуля, можно выполнить только циркулем в том случае, когда исходные и искомые объекты определяются точками. (Так, хотя прямую линию нельзя нарисовать одним циркулем, две точки на этой линии можно определить с помощью пересечения двух окружностей.) В доказательстве Мора примечательно моделирование, с помощью которого он показывает, что любую операцию, в которой участвует линейка, можно заменить конечным числом операций циркуля. Можно ли тут поставить вопрос о близкой связи с теорией автоматов? В этом же русле лежит и результат о том, что линейка, используемая в любом построении, может иметь произвольную положительную длину, и, даже будучи маленькой, все же способна моделировать линейку какой угодно длины.
Лемуан и другие занимались временной сложностью евклидовых построений, и тем не менее также поднимался вопрос об объеме пространства, необходимого для этих построений. Хотя использовавшаяся мера пространства (а именно площадь на плоскости, необходимая для реализации построения) не совпадает с нашим современным определением в смысле количества памяти, занимаемой алгоритмом, она была замечательно близка к нему и весьма естественна. Использованная площадь зависит, вообще говоря, от площади выпуклой оболочки заданных геометрических мест точек и от размера искомого результата, а также от размера любых промежуточных геометрических мест, которые необходимо сформировать при построении [Eves (1972)]. Мы подчеркиваем здесь, что геометрии не чужды представления о времени и памяти.
Когда Галуа продемонстрировал невозможность реализации некоторых евклидовых построений, то стало ясно, что точная трисекция любого угла неосуществима, но нет запрета на выполнимость какого-нибудь приближенного построения. Фактически асимптотически сходящиеся процедуры для квадратуры круга и удвоения куба были известны еще древним грекам [Heath (1921)]. История приближенных алгоритмов, безусловно, является долгой.
14
Гл. I. Введение
1.1.2. Теория выпуклых множеств, метрическая и комбинаторная геометрии
Геометрия XIX века развивалась по многим направлениям. Одно из них, провозглашенное Клейном, включало в себя всестороннее изучение поведения геометрических объектов при различных преобразованиях, а проективная геометрия была его важным ответвлением (см. разд. 1.3.2). Хотя исследование конечных проективных плоскостей приводит к чарующим вопросам и в комбинаторике, и в теории дискретных алгоритмов, этот аспект геометрии не будет предметом данной книги.
Развитие вещественного анализа возымело решающее влияние на геометрию, приведя к формальным абстракциям концепций, которые ранее были лишь интуитивными. Две такие разработки — метрическая геометрия и теория выпуклости — дали главные математические инструменты, которые помогают при построении быстрых алгоритмов.
Расстояние — важное понятие в геометрии. Метрика —его обобщение — дала возможность распространить геометрические концепции и интуицию на анализ, где идея «расстояния» между функциями привела к появлению функциональных пространств и других мощных конструкций. К сожалению, многое из созданного уводило в неконструктивизм. Функциональные пространства по своей природе не вычислимые объекты.
Важность теории выпуклости заключается в том, что она аналитически работает с глобальными свойствами объектов и позволяет нам решать экстремальные задачи. К сожалению, многие вопросы выпуклости имеют громоздкие алгебраические формулировки и субъективно подталкивают к неконструктивным методам.
Комбинаторная геометрия гораздо ближе по духу к нашей цели — алгоритмической геометрии. Она основана на описании геометрических объектов в терминах свойств конечных подмножеств. Например, некоторое множество выпукло тогда и только тогда, когда отрезок, определяемый любой парой его точек, лежит полностью в этом множестве. Неадекватность комбинаторной геометрии для нас заключается в том, что для большинства интересующих нас множеств число их конечных подмножеств бесконечно, а это препятствует их алгоритмической обработке. Работа последних лет в области геометрических алгоритмов направлена на избавление от этих недостатков и развитие математики, ведущей к созданию хороших алгоритмов.
