Вычислительная геометрия
Cтраница 1
Вычислительная геометрия, как она представляется сегодня занимается исследованием вычислительной сложности решения геометрических задач в рамках теории анализа алгоритмов. [1]
В вычислительной геометрии имеется ряд открытых проблем, большинство из которых были упомянуты в статье. Концепция динамической вычислительной геометрии [15, 275], когда рассматриваемые объекты перемещаются с течением ( непрерывным изменением) времени, например, является одним из направлений исследований, заслуживающих дальнейшего изучения. В настоящее время главное внимание в вычислительной геометрии уделяется получению асимптотических оценок поведения алгоритмов. Более чем необходимо проводить сравнения временных характеристик различных алгоритмов, для которых имеется лишь асимптотическая оценка сложности, представленная с помощью 0-большое нотации. Эти сравнения должны проводиться для таких значений размеров исходных данных, какие встречаются в практических задачах. [2]
Наконец, словосочетание вычислительная геометрия для некоторых может означать деятельность в области доказательства геометрических теорем с помощью ЭВМ. Хотя это и увлекательное исследование, но оно дает намного больше информации о наших эвристиках, служащих для доказательства теорем и понимания процедур доказательства, чем данных о геометрии как таковой, и поэтому мы здесь этим заниматься не будем. [3]
Перспективы и методология вычислительной геометрии проясняется, как мы надеемся, при детальном изучении конкретных задач, представленных в данной книге. Одно из основных свойств этой дисциплины заключается в осознании того, что классические характеристики геометрических объектов часто не влияют на проектирование эффективных алгоритмов. Чтобы преодолеть этот недостаток, необходимо найти полезные понятия и установить их свойства, способствующие эффективности вычислений. Короче говоря, вычислительная геометрия должна преобразовать - там, где это необходимо, - классическую дисциплину в ее вычислительную форму. [4]
Для современного состояния вычислительной геометрии типично то, что плоская задача хорошо изучена, но весьма мало известно про случай Е3 и даже еще менее - про случаи большего числа измерений. [5]
 |
Пересечение двух звездных многоугольников. [6] |
Один из главных выводов вычислительной геометрии состоит в том, что большой набор, казалось бы, независимых задач можно решить одним и тем же способом, если только удается выделить общие для них алгоритмические особенности. В данном разделе показано, как множество различных приложений можно унифицировать и свести к решению задачи о том, будут или нет попарно непересекающимися N прямолинейных отрезков из заданного множества. [7]
Дается обзор исследований в области вычислительной геометрии - дисциплины, предметом исследований которой является сложность решения геометрических задач в рамках теории анализа алгоритмов. [8]
Чтобы убедительно продемонстрировать широту приложений вычислительной геометрии, мы отложим представление основного материала по этим задачам до той поры, пока они не встретятся в тексте. [9]
Дается обзор исследований в области вычислительной геометрии - дисциплины, предметом исследований которой является сложность решения геометрических задач в рамках теории анализа алгоритмов. [10]
Богатство математического аппарата и широта применения вычислительной геометрии серьезно осложнили работу над переводом. Определенные трудности создавала также принятая в американской литературе образность терминов, противоречащая сложившейся традиции в русской научно-технической литературе. [11]
У колыбели дисциплины, известной ныне как вычислительная геометрия, стояло большое число приложений, ибо они порождают свойственные им геометрические задачи, для которых должны создаваться эффективные алгоритмы. [12]
Эффективный алгоритм триангуляции имеет многочисленные применения в вычислительной геометрии. Обычно требуется выполнить триангуляцию ( возможно, несколько раз) и некоторую линейную по времени предобработку или постобработку. В этом случае наш алгоритм триангуляции дает оценку О ( п log log n) временной сложности решения всей задачи в целом. [13]
Этот краткий обзор показывает, что методы вычислительной геометрии основаны на достижениях целого ряда областей математики, которые обычно изучаются как самостоятельные математические дисциплины. Поэтому в первых четырех главах настоящей книги мы стремились связать воедино те разделы классической аналитической, алгебраической и дифференциальной геометрии, которые имеют прямое отношение к нашей основной теме, и дать краткий обзор векторной алгебры, ставшей общепринятым языком вычислительной геометрии. Материал этих глав поможет объединить и, мы надеемся, прояснить геометрические аспекты различных методов, применяемых при подгонке и проектировании кривых и поверхностей, которые рассматриваются в гл. [14]
По своему содержанию эта область исследований, названная Форрестом Вычислительная геометрия, ближе к численным методам, чем к геометрии. Цель их работы состоит в определении возможности больших ячеистых структур, составленных из простых цепей, для решения задач распознавания образов. [15]
Страницы: 1 2 3 4