О параллельном алгоритме перечисления триангуляций многоугольника на плоскости
Автор: Попов Владимир Валентинович
Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu
Рубрика: Математика труды III международной конференции "Геометрический анализ и его приложения"
Статья в выпуске: 5 (36), 2016 года.
Бесплатный доступ
В статье описывается параллельный алгоритм перечисления всех триангуляций многоугольника на плоскости. Дается оценка необходимой для реализации алгоритма памяти. Обсуждается быстродействие алгоритма и возможность его применения для компактной записи списка всех трингуляций.
Триангуляция, число триангуляций, дерево триангуляций, оценка объема памяти, число каталана, выпуклая оболочка
Короткий адрес: https://sciup.org/14969031
IDR: 14969031 | DOI: 10.15688/jvolsu1.2016.5.8
Список литературы О параллельном алгоритме перечисления триангуляций многоугольника на плоскости
- Клячин, В.А. Метод цепей для организации хранения многомерных триангуляций/В.А. Клячин, В.В. Попов//Вестник Волгоградского государственного университета. Серия 1, Математика. Физика. -2013. -№ 2 (19). -C. 71-79.
- Попов, В.В. Об алгоритме перечисления триангуляций/В.В. Попов//Вестник Волгоградского государственного университета. Серия 1, Математика. Физика. -2014. -№ 5 (24). -C. 40-45.
- Попов, В.В. Об алгоритме перечисления остовов связного графа/В.В. Попов//Вестник Волгоградского государственного университета. Серия 1, Математика. Физика. -2015. -№ 2 (27). -C. 6-16.
- Попов, В.В. О параллельном алгоритме перечисления триангуляций множества точек плоскости/В.В. Попов//Геометрический анализ и его приложения: материалы III Международной школы-конференции. -Волгоград: Изд-во ВолГУ, 2016. -C. 168-170.
- Препарата, Ф. Вычислительная геометрия: Введение/Ф. Препарата, М. Шеймос. -М.: Мир, 1989. -478 c.
- Скворцов, А.В. Триангуляция Делоне и ее применение/А.В. Скворцов. -Томск: Изд-во Том. ун-та, 2002. -128 c.
- On the Number of Plane Geometrical Graphs/O. Aichholzer, T. Hackl, B. Vogtenhuber, C. Huemer, F. Hurtado, H. Krasser//Graphs and Combinatorics. -2007. -Vol. 23. -P. 67-84. - DOI: 10.1007/s00373-007-0704-5
- Hurtado, F. Graph of triangulations of a convex polygon and tree of triangulations/F. Hurtado, M. Noy//Computational Geometry. -1999. -№ 13. -P. 179-188.
- Polia, G. On picture-writing/G. Polia//The American Mathematical Monthly. -1956. -№ 63. -P. 689-697.
Статья научная
