The optimal algorithm for dynamic support of the Voronoi Diagram for a set of points
DOI:
https://doi.org/10.17721/1812-5409.2020/4.9Анотація
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 - 68
Language of the article: English
Посилання
AGARWAL P. K., MATUSEK, J. (1995). Dynamic half-space range reporting and its applications. Algorithmica. 13. p. 325–345.
BENTLY J. L., SAXE, J. B. (1980). Decomposable searching problems: Static-to-dynamic transformations. J. Algorithms. 1. p. 301–358.
CHAN T. M. (2010) A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. J. ACM. 57(3), # 16.
FORTUNE S. A. Sweepline algorithm for Voronoi diagrams. Algorithmica. 1987. Vol. 2, No. 1-4. P. 153–174.
TERESHCHENKO V. N., BUDJAK I., FISUNENKO A. The Unified Algorithmic Platform for Solving Complex Problems of Computational Geometry, Parallel Computing Technologies. 2013. Vol. 7979. P. 424-429.
SHAMOS M. I., HOEY, D. (1975). Closest-point problems. In 16th Annual IEEE Symposium on Foundations of Computer Science. October 1975. pp. 151–162.
SACK J. R., URRUTIA J., Handbook of Computational Geometry, Elsevier Science, Netherlands (2000).
Завантаження
Номер
Розділ
Ліцензія
Автори, роботи яких публікуються у цьому журналі, погоджуються з такими умовами:
- Автори зберігають авторські права та надають журналу право на першу публікацію роботи, яка одночасно ліцензується згідно із Creative Commons Attribution License, тобто надається дозвіл іншим ділитися роботою з визнанням авторства роботи та першої публікації в цьому журналі.
- Автори можуть укладати окремі додаткові угоди щодо невиключного розповсюдження опублікованої журналом версії роботи (наприклад, розмістити її у репозитарії наукової установи чи опублікувати у книзі) з підтвердженням її початкової публікації у цьому журналі.
- Дозволяється та заохочується розміщення своїх робіт в мережі Інтернет авторами (наприклад, у репозитаріях наукових установ або на особистих веб-сторінках) до та під час процесу подання, оскільки це може призвести до продуктивного обміну, а також до більш ранніх цитувань опублікованої роботи та їх більшої кількості (див. The Effect of Open Access).
