Comparing Data Structures Used in Divide-and-Conquer Three-Dimensional Voronoi Diagrams

被引：0
作者：
Dietsche, Dan [1 ]
Dettling, T. Elise [1 ]
Trefftz, Christian [1 ]
DeVries, Byron [1 ]
机构：
[1] Grand Valley State Univ, Sch Comp, Allendale, MI 49401 USA
来源：
2024 IEEE INTERNATIONAL CONFERENCE ON ELECTRO INFORMATION TECHNOLOGY, EIT 2024 | 2024年
关键词：
Voronoi Diagrams; Divide-and-Conquer; Algorithms;
D O I：
10.1109/eIT60633.2024.10609892
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Voronoi diagrams are used in a wide range of applications, and many of those applications are in three dimensional space. Two important benchmarks you can measure for Voronoi solver algorithms are run time and memory usage. Run time is important due to the potential costs of computation, and memory usage allows for larger areas to be analyzed. Run time can be addressed via parallelization, but memory usage is dependent on data structure. In this paper we compare the run time and memory usage of a previously published 3D Voronoi solver implementation that utilized an array data structure with a new novel implementation that utilizes an oct-tree data structure.
引用
收藏
页码：354 / 358
页数：5
相关论文
共 37 条
  • [1] Divide-and-Conquer for Voronoi Diagrams Revisited
    Aichholzer, Oswin
    Aigner, Wolfgang
    Aurenhammer, Franz
    Hackl, Thomas
    Juettler, Bert
    Pilgerstorfer, Elisabeth
    Rabl, Margot
    PROCEEDINGS OF THE TWENTY-FIFTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'09), 2009, : 189 - 197
  • [2] Divide-and-conquer for Voronoi diagrams revisited
    Aichholzer, Oswin
    Aigner, Wolfgang
    Aurenhammer, Franz
    Hackl, Thomas
    Juettler, Bert
    Pilgerstorfer, Elisabeth
    Rabl, Margot
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2010, 43 (08): : 688 - 699
  • [3] A Divide-and-Conquer Algorithm for Computing Voronoi Diagrams
    Smith, Elijah
    Trefftz, Christian
    DeVries, Byron
    2020 IEEE INTERNATIONAL CONFERENCE ON ELECTRO INFORMATION TECHNOLOGY (EIT), 2020, : 495 - 499
  • [4] Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space
    Setter, Ophir
    Sharir, Micha
    Halperin, Dan
    2009 6TH INTERNATIONAL SYMPOSIUM ON VORONOI DIAGRAMS (ISVD 2009), 2009, : 43 - 52
  • [5] A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
    Bohler, Cecilia
    Liu, Chih-Hung
    Papadopoulou, Evanthia
    Zavershynskyi, Maksym
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2016, 59 : 26 - 38
  • [6] A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams
    Bohler, Cecilia
    Liu, Chih-Hung
    Papadopoulou, Evanthia
    Zavershynskyi, Maksym
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8889 : 27 - 37
  • [7] A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams
    Bohler, Cecilia
    Liu, Chih-Hung
    Papadopoulou, Evanthia
    Zavershynskyi, Maksym
    ALGORITHMS AND COMPUTATION, ISAAC 2014, 2014, 8889 : 27 - 37
  • [8] Divide-and-conquer recurrences associated with generalized heaps, optimal merge, and related structures
    Chen, WM
    Chen, GH
    THEORETICAL COMPUTER SCIENCE, 2003, 292 (03) : 667 - 677
  • [9] An efficient divide-and-conquer approach for big data analytics in machine-to-machine communication
    Ahmad, Awais
    Paul, Anand
    Rathore, M. Mazhar
    NEUROCOMPUTING, 2016, 174 : 439 - 453
  • [10] Data-Driven Divide-and-Conquer for Estimating Build Times of 3D Objects
    Tabassian, Mahdi
    Verbeke, Robbert
    Tourwe, Tom
    Tsiporkova, Elena
    21ST IEEE INTERNATIONAL CONFERENCE ON DATA MINING WORKSHOPS ICDMW 2021, 2021, : 268 - 277
1234