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

Authors

  • V. N. Tereshchenko Taras Shevchenko National University of Kyiv
  • A. A. Marchenko Taras Shevchenko National University of Kyiv
  • Y. V. Tereshchenko Taras Shevchenko National University of Kyiv
  • A. N. Tara Taras Shevchenko National University of Kyiv

DOI:

https://doi.org/10.17721/1812-5409.2020/4.9

Abstract

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

References

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).

No 4 (2020)

Downloads

How to Cite

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. Physical and Mathematical Sciences, (4), 63–68. https://doi.org/10.17721/1812-5409.2020/4.9

Issue

No. 4 (2020)

Section

Computer Science and Informatics

License

Authors who publish with this journal agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).