Cтраница 2
Монография известных американских специалистов, содержащая основы разработки и анализа алгоритмов вычислительной геометрии. Изложение основано на детальном рассмотрении конкретных задач и алгоритмов их решения. Особое внимание уделено способам описания алгоритмов на упрощенном Алголе. [16]
Стандартные структуры данных, рассмотренные выше, широко используются в алгоритмах вычислительной геометрии. Однако природа геометрических задач привела к созданию специальных, необычных структур данных, две из которых оказались настолько общезначимыми, что целесообразно представить их в данной вводной главе. Эти структуры - дерево отрезков и реберный список с двойными связями. [17]
Эту задачу следует рассматривать как одну из фундаментальных задач поиска в области вычислительной геометрии. Она возникает во многих областях науки. Так, например, при классификации образов желательно соотнести заданный образ с одним из классов некоторой конечной совокупности классов. Образы отображаются в точки некоторого пространства, которое разбито на области, каждая из которых соответствует конкретному классу. Классификация осуществляется путем определения области, которой принадлежит классифицируемый образ, и название соответствующего класса и будет ответом. [18]
В элегантной и захватывающей книге, названной Яер-септроны ( подзаголовком которой является также Вычислительная геометрия), Минский и Пейперт [ Minsky, Papert ( 1969) ] изучают сложность предикатов, которые распознают определенные геометрические свойства, такие как выпуклость. [19]
Так, вопросы геометрического моделирования, изучаемые в курсах инженерной графики, основ САПР или в специальном курсе Вычислительная геометрия, полезно дополнить фрагментами соответствующих прикладных протоколов STEP. В главах, посвященных математическому моделированию, нужно знакомить студентов с возможностями многоаспектного моделирования, в том числе на базе языка VHDL-AMS. Студенты должны быть знакомы с методиками концептуального проектирования IDEFO, IDEFIX и объектно-ориентированного проектирования на базе языка UML. Эти вопросы, так же как структура стандартов STEP и основы языка Express, могут быть предметом изучения в отдельном курсе CALS-технологии или в курсе Основы автоматизированного проектирования. В раздел оптимизации проектных решений нужно включить методы оптимального планирования и распределения ресурсов. Наконец, следует предусмотреть знакомство студентов с основами Internet-технологий, в том числе с представлением документов с помощью языков разметки. [20]
Эта задача настолько просто формулируется и настолько важна, что ее можно рассматривать как один из основных вопросов вычислительной геометрии как с точки зрения ее приложений, так и с чисто теоретической точки зрения. Например, одно из приложений этой задачи относится к системе реального времени, управляющей движением самолетов: с некоторыми упрощениями можно считать, что наибольшей опасности столкнуться подвергаются два самолета, находящиеся на наименьшем расстоянии друг от друга. [21]
Цель этой книги-дать обзор основных результатов, полученных за последние тридцать лет в области, которую Форрест ( 1971) назвал вычислительной геометрией, описав ее как представление в ЭВМ, анализ и синтез информации о геометрическом образе. По нашему мнению, в последние годы чисто геометрические начала этой области прикладной математики до некоторой степени затемнены ее вычислительными аспектами. [22]
Задача построения выпуклой оболочки не только оказывается центральной для практических приложений, но является также основой для решения ряда других важных вопросов вычислительной геометрии. [23]
Задача вычисления ( построения) выпуклой оболочки не только является центральной в целом ряде приложений, но и позволяет разрешить ряд вопросов вычислительной геометрии, на первый взгляд не связанных с ней. [24]
Задача построения выпуклой оболочки не только оказывается центральной для практических приложений, но является также основой для решения ряда других важных вопросов вычислительной геометрии. [25]
В дополнение к этим очень важным приложениям возможность выполнять планар-ные триангуляции сама по себе является полезным средством, используемым для решения других задач вычислительной геометрии. Достаточно упомянуть два примера: ( 1) в методе геометрического поиска Киркпатрика ( см. разд. [26]
Книга знакомит с такими основными понятиями и методами компьютерной графики, как трехмерная математика, растровые алгоритмы, непосредственная работа с графическими устройствами, вычислительная геометрия, удаление невидимых линий и поверхностей, текстурирование, построение графического интерфейса, OpenGL. Она дает представление об основных направлениях компьютерной графики и позволяет освоить базовые приемы реализации ее алгоритмов на персональных компьютерах. Приведенные в книге программы могут быть использованы для широкого класса задач. Книгу можно рассматривать как практическое руководство, так как она содержит ряд упражнений, которые способен выполнить прочитавший книгу. [27]
В вычислительной геометрии имеется ряд открытых проблем, большинство из которых были упомянуты в статье. Концепция динамической вычислительной геометрии [15, 275], когда рассматриваемые объекты перемещаются с течением ( непрерывным изменением) времени, например, является одним из направлений исследований, заслуживающих дальнейшего изучения. В настоящее время главное внимание в вычислительной геометрии уделяется получению асимптотических оценок поведения алгоритмов. Более чем необходимо проводить сравнения временных характеристик различных алгоритмов, для которых имеется лишь асимптотическая оценка сложности, представленная с помощью 0-большое нотации. Эти сравнения должны проводиться для таких значений размеров исходных данных, какие встречаются в практических задачах. [28]
Один из подходов заключается в разбиении плоскости на области, в каждой из которых пересечение этих двух многоугольников можно вычислить легко. Построение новых геометрических объектов для решения поставленной задачи не редкость в вычислительной геометрии; читатель может вспомнить исключительное значение этого приема во многих методах геометрического поиска, показанных в гл. [29]
Теперь, имея для сложности алгоритма оценку снизу, рассмотрим вопрос разработки алгоритмов решения задачи о максимумах. Эта задача предоставляет нам великолепную возможность сравнить относительные достоинства и эффективность двух основных парадигм вычислительной геометрии: разделяй и властвуй и заметания по одному из измерений ( см. разд. [30]