Алгоритм - триангуляция
Cтраница 1
 |
Три случая, возникающие на основном шаге. Штриховыми линиями обозначены добавленные диагонали. [1] |
Алгоритм триангуляции обрабатывает по одной вершине за раз в порядке уменьшения у-координаты. [2]
Из множества алгоритмов триангуляции лучшим является тот, при котором получаются треугольники, максимально приближенные к равносторонним. [3]
Примененный при моделировании пластов алгоритм триангуляции заключается в следующем. Все точки ( скважины) в рассматриваемой области соединяются между собой отрезками. Затем отрезки попарно проверяются на пересечение. Если отрезки пересекаются, то выбирается тот из них, который обеспечивает деление четырехугольника, образованного двумя парами вершин, на более равносторонние по указанному выше критерию, другой отрезок становится запрещенным и в дальнейшем сравнении не участвует. Такая выбраковка отрезков позволяет свести зависимость затрат времени Т на триангуляцию от числа точек К к квадратичной форме Т, К1, а не факториальной Т, К. [4]
В этой статье предлагается алгоритм триангуляции с временной сложностью О ( n log log п) и тем самым показывается, что задача триангуляции и в самом деле более легкая, чем задача сортировки. Все попытки разработать алгоритм с линейной сложностью по-прежнему остаются безуспешными, но предлагаемый нами подход определяет несколько направлений для дальнейшего поиска и проясняет те трудности, которые при этом потребуется преодолеть. [5]
К набору массовых точек применяется алгоритм триангуляции Делоне, чтобы создать начальную TIN. Эта TIN отражает общую форму поверхности, но еще не достаточно изображает резкие изменения топографии типа потоков и гребней. [6]
Это с учетом оценки сложности алгоритма вычисления пар видимости и дает суммарную оценку О ( п log log n ] сложности алгоритма триангуляции простого многоугольника. [7]
Следовательно, каждый алгоритм триангуляции может быть использован для сортировки. [8]
Эффективный алгоритм триангуляции имеет многочисленные применения в вычислительной геометрии. Обычно требуется выполнить триангуляцию ( возможно, несколько раз) и некоторую линейную по времени предобработку или постобработку. В этом случае наш алгоритм триангуляции дает оценку О ( п log log n) временной сложности решения всей задачи в целом. [9]
 |
Иллюстрация к получению нижней оценки сложности решения задачи ТРИАНГУЛЯЦИЯ. [10] |
XN, показанное на рис. 5.7. N - 1 точек множества лежат на одной прямой, а одна точка находится вне этой прямой. Триангуляция этого множества может быть выполнена единственным способом, как это показано на рисунке. Список ребер, порождаемый алгоритмом триангуляции, можно использовать для получения упорядоченного списка чисел xi, затратив на это дополнительно О ( N) операций. [11]
Продолжение известной серии сборников, начатой издательством в 1965 г. В данном выпуске содержатся оригинальные и обзорные работы зарубежных ученых по актуальным проблемам теоретической кибернетики и ее приложениям. Большой интерес вызовут статьи К. Тарьяна и др. о сверхбыстрых алгоритмах триангуляции. Включены также работы по теории сложности, алгебраическим схемам отношений и обзор по методам преобразования многоуровневых изображений в двухуровневые. [12]
Страницы: 1