A survey of algorithms for constructing a Delaunay triangulation

Authors

  • A.V. Skvortsov Tomsk Polytechnic University

Keywords:

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

Abstract

A large number of widely used algorithms for constructing a Delaunay triangulation are considered. A classification of these algorithms is proposed. Their performance evaluation is given for the average and worst cases. Some peculiarities of their realization are discussed. Four data structures for the representation of triangulation are analyzed. Several procedures for checking the Delaunay condition and for the triangulation merging are described.

Author Biography

A.V. Skvortsov

References

  1. Делоне Б.Н. О пустоте сферы // Изв. АН СССР, ОМЕН. 1934, 4. 793-800.
  2. Ильман В.М. Алгоритмы триангуляции плоских областей по нерегулярным сетям точек // Алгоритмы и программы. Вып. 10 (88). М., 1985. 3
  3. Ильман В.М. Экстремальные свойства триангуляции Делоне // Алгоритмы и программы. Вып. 10 (88). М., 1985. 57-66.
  4. Костюк Ю.Л., Грибель В.А. Размещение и отображение на карте точечных объектов // Методы и средства обработки сложной графической информации (тезисы докладов всесоюзной конференции). Часть II. Горький, 1988. 60-61.
  5. Кроновер Р.М. Фракталы и хаос в динамических системах. Основы теории / Пер. с англ. М.: Постмаркет, 2000.
  6. Ласло М. Вычислительная геометрия и компьютерная графика на C++ / Пер. с англ. М.: БИНОМ, 1997.
  7. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение / Пер. с англ. М.: Мир, 1989.
  8. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Томского ун-та, 1998. 22-47.
  9. Фукс А.Л. Изображение изолиний и разрезов поверхности, заданной нерегулярной системой отсчетов // Программирование. 1986. 4. 87-91.
  10. Фукс А.Л. Предварительная обработка набора точек при построении триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Томского ун-та, 1998. 48-60.
  11. Bjorke J.T. Quadtrees and triangulation in digital elevation models // International Archives of Photogrammetry and Remote Sensing, International Society for Photogrammetry and Remote Sensing, Committee of the 16th International Congress of ISPRS, Commission IV. Part B4. 1988. 27. 38-44.
  12. Guibas L., Stolfi J. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams // ACM Transactions on Graphics. 1985. 4, N 2. 74-123.
  13. Guttmann A., Stonebraker M. Using a relational database management system for computer aided design data // IEEE Database Engineering. 1982. 5, N 2. 21-28.
  14. Heller M. Triangulation algorithms for adaptive terrain modeling // Proc. of the 4th Intern. Symposium on Spatial Data Handling. 1990. 163-174.
  15. Lawson C. Software for C¹ surface interpolation // Mathematical Software III. NY: Academic Press, 1977. 161-194.
  16. Lawson C. Transforming triangulations // Discrete Mathematics. 1972. 3. 365-372.
  17. Lee D. Proximity and reachability in the plane. Techn. Report R-831. Coordinated Sci. Lab., Univ. of Illinois at Urbana. Urbana, 1978.
  18. Lee D., Schachter B. Two algorithms for constructing a Delaunay triangulation // Int. Jour. Comp. and Inf. Sc. 1980. 9, N 3. 219-242.
  19. Lewis B., Robinson J. Triangulation of planar regions with applications // The Computer Journal. 1978. 21, N 4. 324-332.
  20. Lingas A. The Greedy and Delaunay triangulations are not bad… // Lect. Notes Comp. Sc. 1983. 158. 270-284.
  21. Lloyd E. On triangulation of a set of points in the plain. MIT Lab. Comp. Sc. Tech. Memo. N 88. Boston, 1977.
  22. Manacher G., Zobrist A. Neither the Greedy nor the Delaunay triangulation of planar point set approximates the optimal triangulation // Inf. Proc. Let. 1977. 9, N 1. 31-34.
  23. McCullagh M.J., Ross C.G. Delaunay triangulation of a random data set for isarithmic mapping // The Cartographic Journal. 1980. 17, N 2. 93-99.
  24. Midtbo T. Spatial modeling by Delaunay networks of two and three dimensions. Dr. Ing. thesis. Department of Surveying and Mapping, Norwegian Institute of Technology, University of Trondheim. Trondheim, 1993.
  25. Shapiro M. A note on Lee and Schachter’s algorithm for Delaunay triangulation // Inter. Jour. of Comp. and Inf. Sciences. 1981. 10, N 6. 413-418.
  26. Sibson R. Locally equiangular triangulations // The Computer Journal. 1978. 21, N 3. 243-245.
  27. Watson D.F. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes // The Computer Journal. 1981. 24, N 2. 167-172.

Published

2002-02-15

How to Cite

Скворцов А.В. A Survey of Algorithms for Constructing a Delaunay Triangulation // Numerical methods and programming. 2002. 3. 14-39

Issue

Section

Section 1. Numerical methods and applications