на сайт факультета информатики ТГУ
на сайт Томского государственного университета
  


НАЧАЛО БИБЛИОТЕКА ПУБЛИКАЦИИ СОТРУДНИКОВ ФАКУЛЬТЕТА

     ПУБЛИКАЦИИ СОТРУДНИКОВ ФАКУЛЬТЕТА



Скворцов А. В., Костюк Ю. Л.

Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Вып.1 - Томск: Изд-во Томск. ун-та, 1998, с.22-47,
http://www.inf.tsu.ru/Library/Publications/1999/Skvortsov_1999_1.pdf
Электронная библиотека:




Рассматривается задача построения триангуляции Делоне. Предлагается новый подход к построению алгоритмов слияния, в частности, алгоритмы выпуклого и невыпуклого полосового слияния. Предлагается двухпроходная стратегия построения триангуляции Делоне с откладыванием перестроений. Для улучшения итеративной стратегии построения триангуляции предлагается группа алгоритмов с ускорением поиска треугольников, таких как алгоритмы с изменённым порядком добавления точек (итеративные полосовой и квадратный алгоритмы) и кэширования (алгоритмы статического и динамического кэширования). Для полученных алгоритмов доказывается трудоёмкость, в частности, в среднем O(n) для итеративных полосового и квадратного алгоритмов и для алгоритма динамического кэширования. Предлагается классификация полученных алгоритмов. Приводятся данные экспериментального моделирования работы различных алгоритмов.
Библ. 14, ил. 17, табл. 1.


Формат: Текст PDF Размер: 534 Кбайт
Copyright © 2010 Факультет информатики Томского государственного университета  
  Служба сервера