Диаграммы Вороного на сфере и алгоритм их построения

УДК 519.67 ББК 22.1я431

  • Дмитрий Николаевич Оскорбин Алтайский государственный университет Email: oskorbin@yandex.ru
  • Софья Андреевна Щипцова Алтайский государственный университет Email: sofishipcova@mail.ru
Ключевые слова: диаграммы, диаграммы Вороного, алгоритм Форчуна

Аннотация

В данной работе описано обобщение алгоритма Форчуна для построения диаграммы Вороного множества точек на сфере. Проведена оценка эффективности данного алгоритма.

Биографии авторов

Дмитрий Николаевич Оскорбин, Алтайский государственный университет

кандидат физико-математических наук, институт математики и информационных технологий, доцент

Софья Андреевна Щипцова, Алтайский государственный университет

факультет математики и информационных технологий, студент

Литература

1. Вычислительная геометрия. Алгоритмы и приложения. 3–е изд./Марк де Берг [и др]. – М.: ДМК Пресс, 2017. – 438 с.: ил.

2. A Plane Sweep Algorithm for the Voronoi Tessellation of the Sphere./ Xiaoyu Zheng, Roland Ennis, Gregory P. Richards, Peter PalffyMuhoray // Computational Geometry. –2011. –№2. –P.183 – 194.

3. Joseph O’Rourke. Computational geometry in c./ Joseph O’Rourke. – Cambridge University Press – P. 1994 – 350 с.

4. Скворцов А.В. Алгоритмы построения и анализа триангуляции. / А.В. Скворцов, Н.С Мирза. – Томск.: изд-во Том. ун-та, 2006. – 168с.

5. Steven Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry.Yorktown Heights, New York, United States, pp.313–322. 1986.
Опубликован
2020-09-17
Раздел
Секция ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА