Algorithms for constructing triangulations with constraints

Authors

  • A.V. Skvortsov

Keywords:

триангуляция Делоне
вычислительная устойчивость
вычислительная геометрия
машинная графика
геоинформационные системы
итеративные алгоритмы
выпуклая триангуляция

Abstract

We consider the problem of constructing triangulations with constraints and discuss a number of the corresponding algorithms. The problem of computing stability of these algorithms is studied. A stable modification of the algorithm for constructing a Delaunay triangulation with constraints is proposed.

New computational technologies

Downloads

Published

2002-03-11

Issue

Vol. 3 (2002): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biography

A.V. Skvortsov

Tomsk Polytechnic University,
Institute of Applied Mathematics and Computer Science

References

  1. Делоне Б.Н. О пустоте сферы // Изв. АН СССР, ОМЕН. 1934. 4. 793-800.
  2. Костюк Ю.Л., Фукс А.Л. Приближенное вычисление оптимальной триангуляции // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Томского гос. ун-та, 1998. 61-66.
  3. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение / Пер. с англ. М.: Мир, 1989.
  4. Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование. 2002. 3. 14-39 (http://num-meth.srcc.msu.su).
  5. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Томского гос. ун-та, 1998. 22-47.
  6. Gilbert P.N. New results on planar triangulations. Tech. Rep. ACT-15. Coord. Sci. Lab., University of Illinois at Urbana. Urbana, 1979.
  7. Guttmann A., Stonebraker M. Using a relational database management system for computer aided design data // IEEE Database Engineering. 1982. 5, N 2. 21-28.