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 条

[21] Divide-and-Conquer Solver in Tensor-Train Format for d-Dimensional Time-Space Fractional Diffusion Equations
Yun-Chi Huang
Lot-Kei Chou
Siu-Long Lei
Journal of Scientific Computing, 2023, 96
[22] Divide-and-Conquer Solver in Tensor-Train Format for d-Dimensional Time-Space Fractional Diffusion Equations
Huang, Yun-Chi
Chou, Lot-Kei
Lei, Siu-Long
JOURNAL OF SCIENTIFIC COMPUTING, 2023, 96 (01)
[23] Performance enhancement of deep neural network using fusional data assimilation and divide-and-conquer approach; case study: earthquake magnitude calculation
Esmaeili R.
Kimiaefar R.
Hajian A.
Soleimani-Chamkhorami K.
Hodhodi M.
Neural Computing and Applications, 2024, 36 (27) : 16899 - 16910
[24] Parallel clustering of high dimensional data by integrating multi-objective genetic algorithm with divide and conquer
Tansel Özyer
Reda Alhajj
Applied Intelligence, 2009, 31 : 318 - 331
[25] Parallel clustering of high dimensional data by integrating multi-objective genetic algorithm with divide and conquer
Ozyer, Tansel
Alhajj, Reda
APPLIED INTELLIGENCE, 2009, 31 (03) : 318 - 331
[26] A 3-D Chromosome Structure Reconstruction Method With High Resolution Hi-C Data Using Nonlinear Dimensionality Reduction and Divide-and-Conquer Strategy
Gong, Haiyan
Ma, Fuqiang
Zhang, Xiaotong
Yang, Yi
Li, Minghong
Chen, Zhengyuan
Zhang, Sichen
Chen, Yang
IEEE TRANSACTIONS ON NANOBIOSCIENCE, 2023, 22 (04) : 716 - 727
[27] Constructing the Exact Voronoi Diagram of Arbitrary Lines in Three-Dimensional Space with Fast Point-Location
Hemmer, Michael
Setter, Ophir
Halperin, Dan
ALGORITHMS-ESA 2010, 2010, 6346 : 398 - +
[28] Searching Protein Three-Dimensional Structures in Faster Than Linear Time
Shibuya, Tetsuo
JOURNAL OF COMPUTATIONAL BIOLOGY, 2010, 17 (04) : 593 - 602
[29] The "Gene Cube": A Novel Approach to Three-dimensional Clustering of Gene Expression Data
Lambrou, George I.
Sdraka, Maria
Koutsouris, Dimitrios
CURRENT BIOINFORMATICS, 2019, 14 (08) : 721 - 727
[30] Hardware and software architectures for computationally efficient three-dimensional ultrasonic data compression
Govindan, Pramod
Wang, Boyang
Ravi, Prashaanth
Saniie, Jafar
IET CIRCUITS DEVICES & SYSTEMS, 2016, 10 (01) : 54 - 61

← 1 2 3 4 →