Compression of triangulation topological relations


  • A.V. Skvortsov Tomsk Polytechnic University


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


The problem on packing topological relations of triangles of triangulation is considered. Several modifications of an algorithm for triangle shelling is proposed. On the average, these modifications allow one to achieve the packing density of order 2.12 bits per a triangulation node.

Author Biography

A.V. Skvortsov


  1. Кнут Д. Искусство программирования для ЭВМ. 2. Получисленные алгоритмы. М.: Мир, 1977.
  2. Кнут Д. Искусство программирования для ЭВМ. 3. Сортировка и поиск. М.: Мир, 1978.
  3. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989.
  4. Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование. 2002. 3, № 1. 18-43 (
  5. Chow M.M. Optimized geometry compression for real-time rendering // IEEE Visualization Proceedings. Phoenix. 1997. 347-354.
  6. Deering M. Geometry compression // Computer Graphics. Proceedings of ACM SIGGRAPH. Los Angeles. 1995. 13-20.
  7. Evans F., Skiena S., Varshney A. Optimizing triangle strips for fast rendering // IEEE Visualization Proceedings. San Francisco. 1996. 319-326.
  8. De Floriani L., Magillo P., Puppo E. Compressing triangulated irregular networks // Geoinformatica. 2000. 1, N 4. 67-88.
  9. Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Transactions on Information Theory. 1977. 23, N 3. 337-343.



How to Cite

Скворцов А.В. Compression of Triangulation Topological Relations // Numerical methods and programming. 2002. 3. 124-132



Section 1. Numerical methods and applications