Year: 2010
Numerical Mathematics: Theory, Methods and Applications, Vol. 3 (2010), Iss. 2 : pp. 195–211
Abstract
Efficient data visualization techniques are critical for many scientific applications. Centroidal Voronoi tessellation (CVT) based algorithms offer a convenient vehicle for performing image analysis, segmentation and compression while allowing to optimize retained image quality with respect to a given metric. In experimental science with data counts following Poisson distributions, several CVT-based data tessellation algorithms have been recently developed. Although they surpass their predecessors in robustness and quality of reconstructed data, time consumption remains to be an issue due to heavy utilization of the slowly converging Lloyd iteration. This paper discusses one possible approach to accelerating data visualization algorithms. It relies on a multidimensional generalization of the optimization based multilevel algorithm for the numerical computation of the CVTs introduced in [1], where a rigorous proof of its uniform convergence has been presented in 1-dimensional setting. The multidimensional implementation employs barycentric coordinate based interpolation and maximal independent set coarsening procedures. It is shown that when coupled with bin accretion algorithm accounting for the discrete nature of the data, the algorithm outperforms Lloyd-based schemes and preserves uniform convergence with respect to the problem size. Although numerical demonstrations provided are limited to spectroscopy data analysis, the method has a context-independent setup and can potentially deliver significant speedup to other scientific and engineering applications.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/nmtma.2010.32s.5
Numerical Mathematics: Theory, Methods and Applications, Vol. 3 (2010), Iss. 2 : pp. 195–211
Published online: 2010-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 17
Keywords: Centroidal Voronoi tessellations computational algorithms Lloyd's method acceleration schemes multilevel method binning image analysis visualization signal-to-noise ratio.
-
A Centroidal Voronoi Tessellation Based Visualization Algorithm for Time-Dependent Flow Field
高, 天成
Advances in Applied Mathematics, Vol. 07 (2018), Iss. 01 P.118
https://doi.org/10.12677/AAM.2018.71015 [Citations: 0] -
Fast Methods for Computing Centroidal Voronoi Tessellations
Hateley, James C. | Wei, Huayi | Chen, LongJournal of Scientific Computing, Vol. 63 (2015), Iss. 1 P.185
https://doi.org/10.1007/s10915-014-9894-1 [Citations: 26] -
Mathematics of Planet Earth
Mathematical Challenges in Measuring Variability Patterns for Precipitation Analysis
Emelianenko, Maria | Maggioni, Viviana2019
https://doi.org/10.1007/978-3-030-22044-0_3 [Citations: 1] -
Geometric Self-Assembly of Rigid Shapes: A Simple Voronoi Approach
Larsson, Lisa J. | Choksi, Rustum | Nave, Jean-ChristopheSIAM Journal on Applied Mathematics, Vol. 76 (2016), Iss. 3 P.1101
https://doi.org/10.1137/15M1034167 [Citations: 1] -
Centroidal Voronoi tessellation based methods for optimal rain gauge location prediction
Di, Zichao (Wendy) | Maggioni, Viviana | Mei, Yiwen | Vazquez, Marilyn | Houser, Paul | Emelianenko, MariaJournal of Hydrology, Vol. 584 (2020), Iss. P.124651
https://doi.org/10.1016/j.jhydrol.2020.124651 [Citations: 14] -
A new hybrid adaptive mesh algorithm based on Voronoi tessellations and equi-distribution principle: Algorithms and numerical experiments
Mao, Shaolin
Computers & Fluids, Vol. 109 (2015), Iss. P.137
https://doi.org/10.1016/j.compfluid.2014.12.021 [Citations: 2] -
Enhancing Rendering Performance in Complex Visualizations by using Optimization Techniques and Algorithms in Browser Environments
Brekalo, Sanja | Pap, Klaudio | Trstenjak, BrunoEngineering, Technology & Applied Science Research, Vol. 14 (2024), Iss. 3 P.14049
https://doi.org/10.48084/etasr.7201 [Citations: 0] -
A Simple Geometric Method for Navigating the Energy Landscape of Centroidal Voronoi Tessellations
Gonzalez, Ivan | Choksi, Rustum | Nave, Jean-ChristopheSIAM Journal on Scientific Computing, Vol. 43 (2021), Iss. 2 P.A1527
https://doi.org/10.1137/20M1335534 [Citations: 3]