Open AccessThe optimal algorithm for dynamic support of the Voronoi Diagram for a set of points
Author(s) -
Vasyl Tereshchenko,
A. A. Marchenko,
Yaroslav Tereshchenko,
A. N. Tara
Publication year - 2020
Publication title -
vìsnik. serìâ fìziko-matematičnì nauki/vìsnik kiì̈vsʹkogo nacìonalʹnogo unìversitetu ìmenì tarasa ševčenka. serìâ fìziko-matematičnì nauki
Language(s) - English
Resource type - Journals
eISSN - 2218-2055
pISSN - 1812-5409
DOI - 10.17721/1812-5409.2020/4.9
Subject(s) - voronoi diagram , computer science , data structure , set (abstract data type) , centroidal voronoi tessellation , algorithm , diagram , visualization , dynamic data , data mining , theoretical computer science , mathematics , database , geometry , programming language
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.