Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
1.1.3. Смежные направления
Геометрические по своему характеру алгоритмы разрабатывались в нескольких разных контекстах, и термин «вы-
1.1. Исторический обзор
15
числительная геометрия» уже употреблялся по крайней мере в двух других значениях. Здесь мы попытаемся рассмотреть эти смежные направления в соответствующей перспективе и сопоставить их с современной трактовкой:
1. Геометрическое моделирование средствами сплайновых кривых и поверхностей — предмет, который по духу ближе к численному анализу, чем к геометрии — подробно разрабатывалось Безье, Форрестом и Ризенфельдом. Надо отметить, что Форрест называл свою дисциплину «Вычислительной геометрией» [Bezier (1972), Forrest (1971), Riesenfeld (1973)]1)-
2. В элегантной и захватывающей книге, названной «Пер-септроны» (подзаголовком которой является также «Вычислительная геометрия»), Минский и Пейперт [Minsky, Papert (1969)] изучают сложность предикатов, которые распознают определенные геометрические свойства, такие как выпуклость. Цель их работы заключалась в получении вывода о возможности использования больших сетчаток, состоящих из простых схем, для задач распознавания образов. Их теория полностью самостоятельна и не укладывается в алгоритмические рамки нашей книги.
3. В графическом программном обеспечении и геометрических редакторах широко используются многие алгоритмы, представленные в данной книге. Однако в даннном случае в фокусе оказываются детали реализации и интерфейс с пользователем, а отнюдь не анализ алгоритмов. К этому же классу относятся: программное обеспечение станков с ЧПУ, программы для графопостроителей, картографические системы и программное обеспечение для архитектурного дизайна и строительства.
4. Наконец, словосочетание «вычислительная геометрия» для некоторых может означать деятельность в области доказательства геометрических теорем с помощью ЭВМ. Хотя это и увлекательное исследование, но оно дает намного больше информации о наших эвристиках, служащих для доказательства теорем и понимания процедур доказательства, чем данных о геометрии как таковой, и поэтому мы здесь этим заниматься не будем.
1.1.4. Предыстория вычислительной геометрии
У колыбели дисциплины, известной ныне как вычислительная геометрия, стояло большое число приложений, ибо они порождают свойственные им геометрические задачи, для которых должны создаваться эффективные алгоритмы. К числу таких задач относятся: задача коммивояжера на евклидовой метрике, построение минимального остовного дерева, удаление
') См. также [Фокс, Пратт (1982)]. — Прим. перев.
Гл. 1. Введение
невидимых линий, линейное программирование и многие другие. Чтобы убедительно продемонстрировать широту приложений вычислительной геометрии, мы отложим представление основного материала по этим задачам до той поры, пока они не встретятся в тексте.
Алгоритмические исследования этих и других задач появились в научной литературе в текущем столетии, причем их интенсивность увеличилась в последние два десятилетия. Однако систематическое изучение геометрических алгоритмов было предпринято только совсем недавно и эта дисциплина, окрещенная «вычислительной геометрией» в статье М. Шеймоса [Shamos (1975а)], привлекает к себе все большее число исследователей.
Перспективы и методология вычислительной геометрии проясняется, как мы надеемся, при детальном изучении конкретных задач, представленных в данной книге. Одно из основных свойств этой дисциплины заключается в осознании того, что классические характеристики геометрических объектов часто не влияют на проектирование эффективных алгоритмов. Чтобы преодолеть этот недостаток, необходимо найти полезные понятия и установить их свойства, способствующие эффективности вычислений. Короче говоря, вычислительная геометрия должна преобразовать — там, где это необходимо, — классическую дисциплину в ее вычислительную форму.
1.2. Алгоритмические основы
В течение последних пятнадцати лет анализ и построение вычислительных алгоритмов остаются одной из самых продуктивных областей информатики. Фундаментальные труды Кнута [Knuth (1968; 1973)] и Ахо, Хопкрофта, Ульмана [Aho, Hopcroft, Ullman (1974)] позволили упорядочить и систематизировать богатую коллекцию отдельных результатов; в них сформулированы основные концептуальные модели и установлена методология, ставшая стандартом в этой области. Последующие работы [Reingold, Nievergelt, Deo (1977), Wirth (1976)] укрепили фундамент этой теории.
Поэтому детальный обзор материала этих превосходных книг, с которыми читатель, наверное, основательно знаком, останется за рамками нашей работы. Однако целесообразно — по крайней мере с точки зрения терминологии — привести краткий обзор основных компонент языка, который будет применяться для описания вычислительной геометрии. Эти компоненты суть алгоритмы и структуры данных. Алгоритмы — это программы, исполнимые на удобной абстракции реальных «фон-неймановских» ЭВМ; структуры данных — это способы организации ин-
1.2. Алгоритмические основы
