Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Ф. Препарата
Паоле и Клаудии, а также Юлии
Предисловие
Цель этой книги — единообразное изложение богатых результатов, появившихся в основном за последнее десятилетие в области вычислительной геометрии. Эта молодая дисциплина, названная своим именем в его современном значении одним из нас — М. Шеймосом, привлекла к себе огромный интерес и выросла из набора разрозненных результатов в зрелую область знаний. Достигнутая зрелость, однако, не помешала вычислительной геометрии оставаться постоянным источником научных и прикладных задач.
По мере того, как исследования достигали действительно высокого уровня, с появлением мощных методов и развитием плодотворного взаимодействия с комбинаторной и алгебраической геометрией, возрастала потребность в методически организованном изложении накопленных результатов. Эта потребность ощущалась как в учебной аудитории, где экспериментальные спецкурсы велись на материале журнальных статей и заметок, так и в профессиональной среде, где некоторые прикладные области, такие как автоматизация проектирования, машинная графика, робототехника и т. д., были готовы для восприятия этих результатов.
Данная книга — попытка удовлетворить эту потребность. Задуманная, в основном, как учебное пособие для студентов младших курсов, она ориентирована также на специалистов в вышеупомянутых прикладных областях. Однако необходимо отметить, что эта книга не просто каталог готовых к употреблению методов, хотя некоторые алгоритмы весьма практичны. Наша точка зрения скорее восходит к дисциплине, известной как построение и анализ алгоритмов (или «алгоритмика»), нацеленной на определение трудоемкости решения отдельных задач. Наши исследования в основном направлены на изучение поведения алгоритмов в худшем случае; кроме того, результаты анализа
Предисловие
полностью проявляются лишь для достаточно больших задач (асимптотический анализ). Оба эти момента нельзя упускать из виду при выборе алгоритма, ибо метод, наиболее пригодный для задач малой размерности, не обязательно будет асимптотически оптимальным, а алгоритм не оптимальный в худшем случае, может превзойти другие при оценке его среднего поведения.
Мы попытались дать достаточно детальную панораму непрерывной ветви вычислительной геометрии, а не ее «дискретизи-рованного» варианта. Однако главной целью было систематическое изложение предмета, а не педантичный обзор. Мы пытались частично восполнить этот недостаток в разделах «Замечания и комментарии» в конце каждой главы. Приносим свои извенения многим авторам, чьи работы не были описаны или хотя бы упомянуты.
Начальным ядром книги была докторская диссертация М. Шеймоса. Когда в 1981 г. Р. Грэхем предложил одному из нас (Ф. Препарате) превратить эту исходную рукопись в учебник, никто из нас не представлял себе реальных усилий, которые пришлось затратить впоследствии. К счастью, многие наши коллеги и друзья щедро помогли выполнению этой задачи, терпеливо читая поступающие варианты, предлагая улучшения и вылавливая ошибки. Мы весьма признательны им; и мы рады искренне поблагодарить (в алфавитном порядке): Бентли Дж., Бхаттачарья Б., Ван-Леювена Дж., Вуда Д., Дайера М., Доб-кина Д., Зайделя Р., Каллаи М., Ли Д. Т., Липски-мл. У., О'Рурка Дж., Перлиса А., Рафски Л., Туссена Г., Хоуи Дэна, Чазелле Б., Шульца М., Эйвиса Д., Эйзенстата С. Мы также благодарны за частичную поддержку Национальному научному фонду (субсидия MCS 81-05552 для работы Ф. Препараты), управлению военно-морских исследований, корпорации ИБМ, Университету Карнеги — Меллона и Лабораториям Белла (за работу М. Шеймоса) и руководству издательства «Шпрингер» за энтузиазм, проявленный при сотрудничестве.
Наконец, мы благодарим наших жен, соответственно Розу-Марию и Юлию, за их терпение и поддержку во время тех долгих часов, которые привели к окончательному варианту книги.
Май 1985
Ф. Препарата М- Шеймос
ГЛАВА
Введение
1.1. Исторический обзор
Египетская и греческая геометрия были шедевром прикладной математики. Исходным импульсом для геометрических задач была нужда в точном и справедливом земельном налогообложении, а также в возведении зданий. Как это часто бывает, созданная математика обладала общностью и значением, которые далеко превосходили породившие ее проблемы фараонова департамента налогов, ибо геометрия — это сердцевина математического мышления. Это область, дающая простор интуиции, а новые открытия в ней вполне доступны для неспециалистов.
Принято считать, что главным вкладом Евклида в геометрию является его изложение аксиоматического метода доказательства— утверждение, которое мы не станем оспаривать. Однако для нашего обсуждения важнее изобретение евклидова построения— схемы, состоящей из алгоритма и его доказательства, сплетенных в весьма стилизованном формате. Это евклидово построение удовлетворяет всем требованиям, предъявляемым к алгоритму: оно компактно, корректно и действенно. После Евклида геометрия продолжала процветать, в то время как анализ алгоритмов, к сожалению, попал в 2000-летнюю полосу застоя. Это обстоятельство частично может быть объяснено успехом метода приведения к абсурду, который упрощает математикам доказательство существования некоего объекта путем построения этого доказательства от противного вместо того, чтобы дать точную конструкцию для его получения (алгоритм).
