Algorithms for constructing triangulations with constraints

Authors

  • A.V. Skvortsov Tomsk Polytechnic University

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.

Author Biography

A.V. Skvortsov

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.

Published

2002-03-11

How to Cite

Скворцов А.В. Algorithms for Constructing Triangulations With Constraints // Numerical methods and programming. 2002. 3. 82-92

Issue

Section

Section 1. Numerical methods and applications