[ArXiv] Voronoi Tessellations
As a part of exploring spatial distribution of particles/objects, not to approximate via Poisson process or Gaussian process (parametric), nor to impose hypotheses such as homogenous, isotropic, or uniform, various nonparametric methods somewhat dragged my attention for data exploration and preliminary analysis. Among various nonparametric methods, the one that I fell in love with is tessellation (state space approaches are excluded here). Computational speed wise, I believe tessellation is faster than kernel density estimation to estimate level sets for multivariate data. Furthermore, conceptually constructing polygons from tessellation is intuitively simple. However, coding and improving algorithms is beyond statistical research (check books titled or key-worded partially by computational geometry). Good news is that for computation and getting results, there are some freely available softwares, packages, and modules in various forms.
As a part of introducing nonparametric statistics, I wanted to write about applications of computation geometry from the nonparametric 2/3 dimensional density estimation perspective. Also, the following article came along when I just began to collect statistical applications in astronomy (my [ArXiv] series). This [arXiv] paper, in fact, initiated me to investigate Voronoi Tessellations in astronomy in general.
[arxiv/astro-ph:0707.2877]
Voronoi Tessellations and the Cosmic Web: Spatial Patterns and Clustering across the Universe
by Rien van de Weygaert
Since then, quite time has passed. In the mean time, I found more publications in astronomy specifically using tessellation as a main tool of nonparametric density estimation and for data analysis. Nonetheless, in general, topics in spatial statistics tend to be unrecognized or almost ignored in analyzing astronomical spatial data (I mean data points with coordinate information). Many seem only utilizing statistics partially or not at all. Some might want to know how often Voronoi tessellation is applied in astronomy. Here, I listed results from my ADS search by limiting tessellation in title key words. :
- [arxiv/astro-ph:0110259]
Detecting Clusters of Galaxies in the Sloan Digital Sky Survey I : Monte Carlo Comparison of Cluster Detection Algorithms
by Kim, R.S.J. et al. (2002) AJ, 123, pp.20-36. - [arxiv/astro-ph:0906.1905]
The VOISE Algorithm: a Versatile Toll for Automatic Segmentation of Astronomical Images
by Guio, P. and Achilleos, N. (2009) - Using Voronoi Techniques to determine the shapes of photon sources
by Wilkinson and Meurs Irish Astronomical Journal, 1998, 25(1), 37 - High-order 3D Voronoi tessellation for identifying isolated galaxies, pairs and triplets
by Elyiv, A.; Melnyk, O.; Vavilova, I. 2009..MNRAS..394..1409E - 3-D Voronoi’s Tessellation as a Tool for Identifying Galaxy Groups
by Melnyk, Olga V.; Elyiv, Andrii A.; Vavilova, Iryna B. 2007..IAUS..235..223M - Adaptive binning of X-ray data with weighted Voronoi tessellations
by Diehl, Steven; Statler, Thomas S. 2006..MNRAS..368..497D - Adaptive spatial binning of integral-field spectroscopic data using Voronoi tessellations
by Cappellari, M. and Copin, Y. 2003..MNRAS..342..345C - Adaptive Spatial Binning of 2D Spectra and Images Using Voronoi Tessellations
by Cappellari, M.; Copin, Y. 2002..ASPC..282..515CA - Finding galaxy clusters using Voronoi tessellations
by Ramella, M.; Boschin, W.; Fadda, D.; Nonino, M. 2001..A&A…368..776R - The Forest Method as a New Parallel Tree Method with the Sectional Voronoi Tessellation
by Yahagi, Hideki; Mori, Masao; Yoshii, Yuzuru 1999..ApJS..124..1 - Cluster Identification via Voronoi Tesselation ..1999..ASPC..176..108
- The accuracy of parameters determined with the core-sampling method: Application to Voronoi tessellations 1997..A&AS..123..495
- Dynamical Voronoi tessellation. V. Thickness and incompleteness.
by Zaninetti, L 1995..A&AS..109..71 - Fragmenting the Universe. 3: The constructions and statistics of 3-D Voronoi tessellations
by van de Weygaert, Rien 1994..A&A..283..361 - Dynamical Voronoi tessellation. IV. The distribution of the asteroids
by Zaninetti, L 1993..A&A..276..255 - Quasi-periodic structures in the large-scale galaxy distribution and three-dimensional Voronoi tessellation
1991..MNRAS..250..519 - Dynamical Voronoi tessellation. III – The distribution of galaxies
by Zaninetti, L 1991..A&A..246..291 - Dynamical Voronoi tessellation. II – The three-dimensional case
by Zaninetti, L 1990..A&A..233..293 - Dynamical Voronoi tessellation. I – The two-dimensional case
by Zaninetti, L 1989..A&A..224..345
Then, the topic has been forgotten for a while until this recent [arXiv] paper, which reminded me my old intention for introducing tessellation for density estimation and for understanding large scale structures or clusters (astronomers’ jargon, not the term in machine or statistical learning).
[arxiv:stat.ME:0910.1473] Moment Analysis of the Delaunay Tessellation Field Estimator
by M.N.M van Lieshout
Looking into plots of the papers by van de Weygaert or van Lieshout, without mathematical jargon and abstraction, one can immediately understand what Voronoi and Delaunay Tessellation is (Delaunay Tessellation is also called as Delaunay Triangulation (wiki). Perhaps, you want to check out wiki:Delaunay Tessellation Field Estimator as well). Voronoi tessellations have been adopted in many scientific/engineering fields to describe the spatial distribution. Astronomy is not an exception. Voronoi Tessellation has been used for field interpolation.
van de Weygaert described Voronoi tessellations as follows:
- the asymptotic frame for the ultimate matter distribution,
- the skeleton of the cosmic matter distribution,
- a versatile and flexible mathematical model for weblike spatial pattern, and
- a natural asymptotic result of an evolution in which low-density expanding void regions dictate the spatial organization of the Megaparsec universe, while matter assembles in high-density filamentary and wall-like interstices between the voids.
van Lieshout derived explicit expressions for the mean and variance of Delaunay Tessellatoin Field Estimator (DTFE) and showed that for stationary Poisson processes, the DTFE is asymptotically unbiased with a variance that is proportional to the square intensity.
We’ve observed voids and filaments of cosmic matters with patterns of which theory hasn’t been discovered. In general, those patterns are manifested via observed galaxies, both directly and indirectly. Individual observed objects, I believe, can be matched to points that construct Voronoi polygons. They represent each polygon and investigating its distributional properly helps to understand the formation rules and theories of those patterns. For that matter, probably, various topics in stochastic geometry, not just Voronoi tessellation, can be adopted.
There are plethora information available on Voronoi Tessellation such as the website of International Symposium on Voronoi Diagrams in Science and Engineering. Two recent meeting websites are ISVD09 and ISVD08. Also, the following review paper is interesting.
Centroidal Voronoi Tessellations: Applications and Algorithms (1999) Du, Faber, and Gunzburger in SIAM Review, vol. 41(4), pp. 637-676
By the way, you may have noticed my preference for Voronoi Tessellation over Delaunay owing to the characteristics of this centroidal Voronoi that each observation is the center of each Voronoi cell as opposed to the property of Delaunay triangulation that multiple simplices are associated one observation/point. However, from the perspective of understanding the distribution of observations as a whole, both approaches offer summaries and insights in a nonparametric fashion, which I put the most value on.
Leave a comment