Алгоритмы в вычислительной геометрии

1.Теория выпуклых множеств.Метрическая и комбинаторная геометрии

     Разумный человек приспосабливается к миру; 
     неразумный  упорно пытается приспособить мир к себе. 
     Поэтому прогресс зависит от неразумных людей. 
     
Б. Шоу
     

Предлагаемые Вам статьи задуманы и посвящены довольно интересному на мой взгляд и мало освещённому в русскоязычном Интернете вопросу-вопросу вычислительной геометрии. Я лично отнюдь не претендую на авторство той информации ,которую я дерзаю Вам предлагать. Основной мой источник-это книга (нераспространённая ,надо полагать,так как я у себя в университете её не нашёл) Ф.Препарата и М.Шеймос "Вычислительная геометрия". В своё время я для своей научно-исследовательской работы долго рыскал по Интернету в поисках математически обоснованных и более-менее прилично изложенных алгоритмов вычислительной геометрии, поскольку большинство сайтов или предлагает куски весьма отвлечённого кода на каком-то языке, сопровождаемого выражениями типа "компильнул прогу" или "топтал клаву" и т.п., или вообще крайне скудную информацию. Тем не менее я позволю себе упомянуть весьма солидную библиотеку алгоритмов на сайте www.algolist.manual.ru, а также довольно неплохой ресурс www.alglib.manual.ru. Книга Ф.Препарата и М.Шеймоса выгодно отличается от большинства информации в сети строгостью изложения, а также довольно неудачной( на мой взгляд ) попыткой иллюстрации алгоритмов на языке Algol.Я надеюсь, что у меня получится передать на HTML все достоинства книги, а приводимые алгоритмы я в силу своих скромных способностей буду иллюстрировать на Object Pascal. Итак, я надеюсь, что мои статьи принесут Вам пользу.Удачи!

Ваши предложения и замечания я жду по адресу:shershzzz@mail.ru. Шморгун Евгений,ДонНТУ

Многие изложения принято начинать с истории.Я не буду исключением и замечу, что геометрия XIX века развивалась по многим направлениям. Один из известных математиков того времени(Клейн) провозгласил своё мнение, согласно которому изучать надлежит поведение геометрических объектов при различных преобразованиях.Большую, хотя и второстепенную должна была играть в этом проективная геометрия.Не будем спорить о правильности или,вернее,своевременности этого утверждения,но развитие вещественного анализа оказало настолько могучее влияние на геометрию, что привела математиков к формальным абстракциям концепций,которые ранее были приняты ими лишь на интуитивном уровне. Именно тому времени мы обязаны появлением мощных математических инструментов для конструирования быстрых геометрических алгоритмов-метрической геометрии и теорией выпуклости.

Что такое расстояние? Каждый может дать свой ответ на этот вопрос-можно услышать всё, начиная от маловразумительных объяснений не инженеров и математиков, до, быть может, известной формулы евклидового расстояния. Математика даёт более глубокое обобщение понятия расстояния термином -метрика.Это дало возможность распространить геометрические концепции и интуицию на анализ, где идея "расстояния" между функциями привела к созданию мощного аппарата функциональных пространств.К сожалению, многое из созданного в тот период уводило математиков в неконструктивизм, поскольку математическая природа функциональных пространств неисчислима.

Теория выпуклости важна, поскольку она позволяет работать нам с глобальными свойствами объектов и решать экстремальные задачи.Но и здесь многие формулировки имеют крайне громоздкий вид и явно или неявно подталкивают математиков к неконструктивным методам.

С другой стороны, комбинаторная геометрия основана на описании геометрических объектов в терминах конечных подмножеств.Классический пример, следующая теорема-некоторое множество выпукло тогда и только тогда, когда отрезок, определяемый любыми двумя точками этого множества,полностью принадлежит этому же множеству.Тем не менее для нас,интересующихся с тех или иных позиций алгоритмической обработкой геометрических данных, и здесь существует определённый недостаток.Этот недостаток состоит в том, что для большинства необходимых нам множеств число их конечных подмножесв бесконечно, а это является препятствием при алгоритмической обработке и накладывает определённые ограничения.В последние годы математики этой области трудятся над устранением этого недостатка и созданием хороших и быстрых алгоритмов.

2.Смежные направления

За то время, когда алгоритм сам по себе стал объектом исследования, геометрические алгоритмы разрабатывались различными математиками в различных направлениях.Эти направления(как упомянуто в заголовке-смежные направления) имели следующий характер:

• Геометрическое моделирование средствами сплайновых кривых и поверхностей.Изучавшие эту область математики согласятся с тем, что она ближе к численному анализу, чем к геометрии. Следует отметить здесь работы Безье,Форреста,Розенфельда.
• Также имеется книга "Персептроны" Минского и Пайперта, в которой они изучают сложность предикатов, которые распознают определённые геометрические свойства(например,выпуклость). Цель работы состояла в получении вывода о возможности использования больших сетчаток, состоящих из простых схем, для распознавания образов.Эта работа носит очень глубокий и самостоятельный характер и рассматриваться мною не будет.
• В самом различном программном обеспечении широко используются многие алгоритмы, которые Вы сможете изучить по дальнейшим моим статьям.Но,как указывают Препарата и Шеймос, наибольшее внимание по данному вопросу уделено деталям реализации и интерфейсу с пользователем, а не анализу алгоритмов.Сюда можно отнести программы графопостроителей, картографические системы, геоинформационные системы и т.д.
• "Вычислительная геометрия" наталкивает на мысль о доказательствах геометрических теорем на ЭВМ.Но, опять таки согласно Препарате и Шеймосу, это занятие способствует информации о доказательствах теорем и понимания процедур доказательства как таковых, и поэтому я это не рассматриваю.

3.История вычислительной геометрии

Как и у любой другой дисциплины, у истоков вычислительной геометрии стояло много самых различных приложений,благодаря которым появилось большое число задач, что, в свою очередь, и породило создание и развитие аппарата алгоритмов.Можно назвать известные всем задачи (вы определённо встречали их в курсах дискретной математики):задача коммивояжёра, задача построения минимального остовного дерева,задача удаления невидимых линий, задачи линейного программирования и многие другие.Алгоритмические исследования подобных задач появились в литературе лишь в текущем (вернее сказать, уже в прошедшем) столетии.Это связано прежде всего с тем с появлением многих приложений, которые требовали совершенно особого подхода.Этот особый подход выявился в созданной Аланом Тьюрингом теории искусственного интеллекта, а также в появлении теории информации.

Пока математика имела дело в основном с числами и вычислениями, то понятия алгоритма интуитивно отождествлялось с понятием метода вычисления, а необходимость в изучении самого понятия алгоритм не утверждалась.По-видимому это происходило потому, что традиции организации вычислений складывались веками и стали частью общей научной культуры, как и элементарные навыки логического мышления(переучить Вас со сложения чисел в столбик для вычисления суммы на нахождение мощности множества двух подмножеств будет крайне нелегко,если Вы не Георг Кантор).В своём развитии математика накопила огромнейшее количество алгоритмов, но всё разнообразие вычислений комбинировалось из небольшого числа чётко определённых операций арифметики, тригонометрии и анализа.Благодаря этому понятие метода вычислений считалось интуитивно понятным и не требующим специальных исследований.

Дальнейший процесс развития вычислительных методов помог утвердиться мысли о том, что решение любой проблемы должно быть алгоритмичным.Этой мысли придерживались такие известные математики как Р.Декарт, Г.Лейбниц, Д.Гильберт.Благодаря последнему активизировались алгоритмические исследования. Вы знаете о 23 знаменитых проблемах Гильберта, которые были сформулированы им в 1900 году на Международном математическом конгрессе.Десятая проблема Гильберта звучит так:дано алгебраическое уравнение с целыми коэффициентами.Необходимо найти метод, с помощью которого можно было бы за конечное число операций установить, имеет ли уравнение решение в целых числах.Этот метод понимают сейчас как алгоритм.

В то время теория алгоритмов ещё не была создана( не было как таковой и вычислительной геометрии, хотя задача коммивояжёра решалась!) и речь могла идти лишь о позитивном или негативном решении десятой проблемы Гильберта.Однако, в 1970 году советский математик Ю.В.Матиясевич доказал, что такого алгоритма нет.Тем не менее, первые мысль о том, что идея универсальности алгоритмического решения любой задачи ошибочна, появилась в 1931 году после работы К.Геделя "О формально нерешаемых утверждениях principia mathematica и объединённых систем".В работе было показано, то существуют такие математические проблемы, оторые не могут быть решены с помощью алгоритмов из некоторого определённого класса алгоритмов(простите за тавтологию).

В качестве заключения о истории алгоритмов сформулирую две точки зрения, которые существовали в математике до уточнения понятия "алгоритм":

• Все проблемы алгоритмически разрешаемы.Однако алгоритм для решения конкретных задач ещё просто не найден, потому что в математике просто пока нет средств для построения математической основы алгоритма.То есть, создание искомых алгоритмов-дело будущего...
• Есть классы задач,для решения которых нет алгоритма вообще.Существуют проблемы, которые невозможно решать с помощью формальных размышлений и вычислений.Требуется творческое мышление!Это очень сильное утверждение, поскольку оно распространяется на все будущее время.

Пока определение алгоритма зиждилось на интуитивном представлении, о математическом доказательстве второго утверждения не могло быть и речи.Благодаря появлению гипотез о существовании стандартных форм, с помощью которых могут быть выражены любые алгоритмы, стало возможным сформулировать понятие "алгоритм" и "алгоритмически нерешаемая проблема" в точных математических терминах.Здесь мы с Вами приходим к очень важной для нас мысли: классические характеристики геометрических объектов часто не влияют на проектирование эффективных алгоритмов.Следует найти полезные понятия и установить их свойства, способствующие эффективности вычислений.Как говорят Препарата и Шеймос "вычислительная геометрия должна преобразовать-там, где это необходимо,-классическую дисциплину в в её вычислительную форму".