PDF(1064 KB)
A Generic Statistics-Based Tessellation Method of Voronoi Diagram
Shun KANG
系统科学与信息学报(英文) ›› 2015, Vol. 3 ›› Issue (6) : 568-576.
PDF(1064 KB)
PDF(1064 KB)
A Generic Statistics-Based Tessellation Method of Voronoi Diagram
A Generic Statistics-Based Tessellation Method of Voronoi Diagram
In terms of distance function and spatial continuity in Voronoi diagram, a generic generating method of Voronoi diagram, named statistical Voronoi diagram, is proposed in this paper based upon statistics with mean vector and covariance matrix. Besides, in order to make good on the discreteness of spatial Voronoi cell, the cross Voronoi cell accomplished the discrete ranges in its continuous domain. In the light of Mahalanobis distance, not only ordinary Voronoi and weighted Voronoi are implemented, but also the theory of Voronoi diagram is improved further. Last but not least, through Gaussian distribution on spatial data, the validation and soundness of this method are proofed by empirical results.
In terms of distance function and spatial continuity in Voronoi diagram, a generic generating method of Voronoi diagram, named statistical Voronoi diagram, is proposed in this paper based upon statistics with mean vector and covariance matrix. Besides, in order to make good on the discreteness of spatial Voronoi cell, the cross Voronoi cell accomplished the discrete ranges in its continuous domain. In the light of Mahalanobis distance, not only ordinary Voronoi and weighted Voronoi are implemented, but also the theory of Voronoi diagram is improved further. Last but not least, through Gaussian distribution on spatial data, the validation and soundness of this method are proofed by empirical results.
Voronoi / statistics / covariance / discreteness / Mahalanobis {{custom_keyword}} /
Voronoi / statistics / covariance / discreteness / Mahalanobis {{custom_keyword}} /
[1] Voronoi G. Nouvelles applications des paramètres continues à la théorie des formes quadratiques. Journal für die Reine und Angewandte Mathematik, 1908, 134:198-287.
[2] Aurenhammer F. Voronoi diagrams-A survey of a fundamental geometric data structure. ACM Computing Surveys, 1991, 23(3):345-405.
[3] Dong P. Generating and updating multiplicatively weighted Voronoi diagrams for point, line and polygon features in GIS. Computers & Geosciences, 2008, 34(4):411-421.
[4] Aurenhammer F, Edelsbrunner H. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition, 1984, 17(2):251-257.
[5] Du Q, Faber V, Gunzburger M. Centroidal Voronoi tessellations:Applications and algorithms. SIAM Review, 1999, 41(4):637-676.
[6] Ju L, Du Q, Gunzburger M. Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations. Parallel Computing, 2002, 28(10):1477-1500.
[7] Boissonnat J, Nielsen F, Nock R. Bregman Voronoi diagrams. Discrete & Computational Geometry, 2010, 44(2):281-307.
[8] Sud A, Fisher D, Lee H. Fast dynamic Voronoi treemaps. ISVD 2010-7th International Symposium on Voronoi Diagrams in Science and Engineering, 2010, 85-94.
[9] Chen J. Voronoi-based dynamic spatial data model. Beijing:Publishing House of Surveying and Mapping, 2002.
[10] Chen J, Li C, Li Z, et al. A Voronoi-based 9-intersection model for spatial relations. International Journal of Geographical Information Science, 2001, 15(3):201-220.
[11] Chen J, Zhao R, Li Z. Voronoi-based k-order neighbour relations for spatial analysis. ISPRS Journal of Photogrammetry and Remote Sensing, 2004, 59(1-2):60-72.
[12] Chen J, Zhao X, Li Z. An algorithm for the generation of Voronoi diagrams on the sphere based on QTM. Photogrammetric Engineering and Remote Sensing, 2003, 69(1):79-89.
[13] Zhao R. Voronoi methods for computing spatial relations in GIS. Beijing:Publishing House of Surveying and Mapping, 2006.
[14] Li J, Chen J, Zhao R, et al. A backward inflation generating method for Voronoi diagram based on linear quadtree structure. Acta Geodaetica et Cartographica Sinica, 2008, 37(2):236-242.
[15] Hu S, Jin L, Donguk K, et al. A sweepline algorithm for Euclidean Voronoi diagram of circles. Computer Aided Design, 2002, 38(3):260-272.
[16] Ai T, Yu W. Algorithm for constructing network Voronoi diagram based on flow extension ideas. Acta Geodaetica et Cartographica Sinica, 2013, 42(5):760-776.
[17] Shi W. Principles of modeling uncertainties in spatial data and spatial analyses. CRC Press, 2009:8-12.
[18] Zhang J, Yang Y. Analysis on the status of spatial data uncertainty research. Geospatial Information, 2009, 7(3):4-8.
[19] Ren X, Yu X. Multivariable statistical analysis. Beijing:China Statistics Press, 2011:63-65.
[20] Li D, Wang S, Li D, et al. Theories and technologies of spatial data mining and knowledge discovery. Geomatics and Information Science of Wuhan University, 2002, 27(3):221-233.
[21] Fisher R. On the mathematical foundations of theoretical statistics. Philosophical Transactions of the Royal Society, 1922, A:222:309-368.
[22] Balzer M, Deussen O. Voronoi treemaps. Proceedings of IEEE Symposium on Information Visualization, INFO VIS, 2005:49-56.
[23] Richard A, Dean W. Applied multivariable statistical analysis. United States:Prentice Hall, 2001:22-27.
[24] Mahalanobis P C. On the generalized distance in statistics. Proceedings of the National Institute of Science of India, 1936, 12:49-55.
/
| 〈 |
|
〉 |
