Метод цепей для организации хранения многомерных триангуляций
Автор: Клячин Владимир Александрович, Попов Владимир Валентинович
Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu
Рубрика: Прикладная математика
Статья в выпуске: 2 (19), 2013 года.
Бесплатный доступ
Рассматривается задача о поиске наилучшего способа записи триангуляции конечного набора точек многомерного пространства. В работе дана формальная постановка задачи. Приведены примеры для сравнения различных способов представления триангуляций. Так же в статье приводится алгоритм, перебирающий все триангуляции произвольного конечного набора точек на плоскости.
Триангуляция, симплекс, оценка объема памяти, число триангуляций, число каталана
Короткий адрес: https://sciup.org/14968738
IDR: 14968738
Список литературы Метод цепей для организации хранения многомерных триангуляций
- Делоне, Б. Н. О пустой сфере. К мемуару Георгия Вороного/Б. Н. Делоне; пер. с фр.: А. Ю. Игумнов//Записки семинара «Сверхмедленные процессы». -2005. -Вып. 1. -С. 147-153.
- Скворцов, А. В. Алгоритмы построения и анализа триангуляции/А. В. Скворцов, Н. С. Мирза. -Томск: Изд-во Томск. ун-та, 2006. -168 с.
- Ajtai, М. Crossing-free subgraphs/M. Ajtai, V. Chvátal, M. M. Newborn, E. Szemerédi//Annals Discrete Math. -1982. -№ l2. -P. 9-12.
- De Floriani, L. Compressing Triangulated Irregular Networks/L. De Floriani, P. Magillo, E. Puppo//Geoinformatica. -2000. -V. 1, № 4. -P. 67-88.
- Delaunay, В. N. Sur la sphere vide. Â la memoire de Georges Voronoi/B. N. Delaunay//Изв. АН СССР. -1934. -№ 6. -C. 793-800.
- Denny, M. О. Encoding a triangulation as a permutation of its point set/M. O. Denny, C. Â. Sohler//Proc. 9th Canadian Conf. on Computational Geometry. -1997. -P. 39-43.
- Pólya, G. On picture-writing/G. Polya//The American Mathematical Monthly. -1956. -№ 63. -P. 689-697.
- Santos, F. A better upper bound on the number of triangulations of a planar point set/F. Santos, R. Seidel//J. Combinat. Theory, Ser. A. -2003. -№ 102. -P. 186-l93.
- Seidel, R. On the number of triangulations of planar point sets/R. Seidel//Combinatorica. -1998. -№ 18. -P. 297-299.
- Sharir, M. Random triangulations of planar point sets/M. Sharir, E. Welzl//Proc. 22nd Ann. ÂCM Symp. on Computational Geometry. -2006. -P. 273-281.
- Smith, W. S. Studies in Computational Geometry Motivated by Mesh Generation: Ph.D. Thesis/W. S. Smith. -Princeton University, 1989. -488 p.
Статья научная
