Dynamic Construction of Voronoi Diagram for a Set of Points and Straight Line Segments

Abstract:

Voronoi Diagram for a set of points and straight line segments is difficult to construct because general figures have uncertain shapes^[. In traditional algorithm, when generator of general figure changes, production process will be extremely complex because of the change of regions neighboring with those generator changed. In this paper, we use dynamicconstruction of Voronoi diagrams. The algorithm can get over all kinds of shortcomings that we have just mentioned. So it is more useful and effective than the traditional algorithm^[2]. The results show that the algorithm is both simple and useful, and it is of high potential value in practice.

• Periodical: Applied Mechanics and Materials (Volume 533)
• Pages: 264-267
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.533.264
• Online since: February 2014
• Authors: Xin Liu*
• Keywords: Dynamic Construction, Voronoi Diagram, Voronoi Diagram for a Setof Points and Straight Line Segments

References

[1] Kazuhiro Yamada and Kokichi Sugihara. Approximation of Voronoi diagrams for figures and its improvement, Department of Mathematical Engineering and Information Physics, Graduate School of Engineering, University of Yokyo, (1996).

[2] Takafumi Watanabe and Sadayuki Murashima. A method to construct a Voronoi diagram on 2-D digitized space (1) computing time, . Faculty of Engineering, Kagoshima.

[3] Voronoi,G. Nouvelles. applications des parameters continues a la theorie des formes quadratiques, Deuxieme memoire: Recherches sur les parplleloedres primitives. Math, 1908, (134): 198-287.

DOI: 10.1515/crll.1908.134.198

[4] Edetsbrunner H. Smooth surfaces for multiscale shaperepresentation, , Proceedings of the 15th Conference on Foundations of Software Technology and Theoretical Computer Science, Bangalore, 1995. 391-412.

[5] Yang Cheng-Lei, Wang Jia-Ye, Meng Xiang-Xu,. Upper Bounds on the Size of Inner Voronoi Diagrams of Multiply Connected Polygons, Journal of Software, 2006. 7, 17(7): 1527-1534.

DOI: 10.1360/jos171527

[6] Jun Chen, Renliang Zhao, Zhilin Li.: Voronoi-based k-order neighbour relations for spatial analysis. J. ISPRS Journal of Photogrammetry and Remote Sensing. 59, 60—72 (2004).

DOI: 10.1016/j.isprsjprs.2004.04.001

[7] Ickjai Lee, Kyungmi Lee.: A generic triangle-based data structure of the complete set of higher order Voronoi diagrams for emergency management. Computers, Environment and Urban Systems. 33, 90-99 (2009).

DOI: 10.1016/j.compenvurbsys.2009.01.002

[8] S. Cabello, M. Fort, J.A. Sellarès.: Higher-order Voronoi diagrams on triangulated surfaces. J. Information Processing Letters. 109, 440-445 (2009).

DOI: 10.1016/j.ipl.2009.01.001

[9] Yugong Wu, Weibin Zhou, Bu Wang, Fan Yang.: Modeling and characterization of two-phase composites by Voronoi diagram in the Laguerre geometry based on random close packing of spheres. Computational Materials Science. 47, 951-96, (2010).

DOI: 10.1016/j.commatsci.2009.11.028

[10] Ye Zhao, Shujuan Liu, Youhui Zhang. Spatial Density Voronoi Diagram and Construction. Journal of Computers. Vol 7, (2012), 2007-2014, Aug (2012).

[11] Wu Ran, Ye Zhao. Discrete Construction of Network Voronoi Diagram. ICMCI'2010. : 630-632.