The optimal algorithm for dynamic support of the Voronoi Diagram for a set of points

Tereshchenko, V. N.; Marchenko, A. A.; Tereshchenko, Y. V.; Tara, A. N.

doi:10.17721/1812-5409.2020/4.9

The optimal algorithm for dynamic support of the Voronoi Diagram for a set of points

Тип публікації :

Стаття

Дата випуску :

2020

Автор(и) :

Tereshchenko, V. N.

Marchenko, A. A.

Tereshchenko, Y. V.

Tara, A. N.

Мова основного тексту :

Англійська

eKNUTSHIR URL :

https://ir.library.knu.ua/handle/15071834/26181

DOI :

10.17721/1812-5409.2020/4.9

Журнал :

Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics

Випуск :

4

ISSN :

1812-5409

Початкова сторінка :

63

Кінцева сторінка :

68

Цитування :

[APA 7] Tereshchenko, V. N., Marchenko, A. A., Tereshchenko, Y. V., & Tara, A. N. (2020). The optimal algorithm for dynamic support of the Voronoi Diagram for a set of points. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics, (4), 63–68. https://doi.org/10.17721/1812-5409.2020/4.9

[ДСТУ] The optimal algorithm for dynamic support of the Voronoi Diagram for a set of points / V. N. Tereshchenko et al. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics. 2020. no. 4. P. 63—68. DOI: 10.17721/1812-5409.2020/4.9 (date of access: 18.07.2026).

The article is devoted to the development of a dynamic data structure for solving proximity problems based on the dynamic Voronoi Diagram. This data structure can be used as the core of the common algorithmic space model for solving a set of visualization and computer modeling problems.The data structure is based on the strategy of "divide and rule" for Voronoi diagram construction. Similar to the original algorithm, we store a binary tree that represents the Voronoi diagram, but define three new operations: insert, delete, and balance. To ensure the efficiency of operations, it is proposed to use red-black tree. In general, the proposed data structure shows much better results than the original static algorithm. Compared to existing algorithms, this data structure is both simple and efficient.Key words: dynamic data structures, algorithm, divide and conquer, Voronoi diagram, nearest neighbour, model of common algorithmic space.Pages of the article in the issue: 63 - 68Language of the article: English

Файл(и) :

Завантажити

Формат :

Adobe PDF

Розмір :

714.3 KB

Контрольна сума :

(MD5):7b1eeefc0e8302f979cb1cf107704a68

Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution 4.0 International