Abstract
Circles are frequently used for modelling the growth of particle aggregates through the Johnson-Mehl tessellation, that is a special instance of the Voronoi diagram of circles. Voronoi diagrams allow one to answer proximity queries after locating a query point in the Voronoi zone it belongs to. The dual graph of the Voronoi diagram is called the Delaunay graph. In this paper, we first show a necessary and sufficient condition of connectivity of the Voronoi diagram of circles. Then, we show how the Delaunay graph of circles (the dual graph of the Voronoi diagram of circles) can be computed exactly, and in a much simpler way, by computing the eigenvalues of a two by two matrix. Finally, we present how the Voronoi diagram of circles can be used to model the growth of particle aggregates. We use the Poisson point process in the Voronoi diagram of circles to generate the Johnson-Mehl tesselation. The Johnson-Mehl model is a Poisson Voronoi growth model, in which nuclei are generated asynchronously using a Poisson point process, and grow at the same radial speed. Growth models produce spatial patterns as a result of simple growth processes and their visualization is important in many technical processes.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Ash, P.F., Bolker, F.D.: Generalized Dirichlet Tessellations. Geometria Dedicata 20, 209–243 (1986)
Anton, F., Boissonnat, J.-D., Mioc, D., Yvinec, M.: An exact predicate for the optimal construction of the Additively Weighted Voronoi diagram. In: Proceedings of the European Workshop on Computational Geometry 2002, Warsaw, Poland (2002)
Aurenhammer, F., Klein, R.: Voronoi diagrams. In: Handbook of computational geometry, pp. 201–290. North-Holland, Amsterdam (2000)
Anton, F., Kirkpatrick, D., Mioc, D.: An exact algebraic predicate for the maintenance of the topology of the additively weighted voronoi diagram. In: The Fourteenth Canadian Conference on Computational Geometry, Lethbridge, Alberta, Canada, pp. 72–76 (2002)
Anishchik, S.V., Medvedev, N.N.: Three-dimensional Apollonian packing as a model for dense granular systems ll. Phys. Rev. Lett. 75(23), 4314–4317 (1995)
Anton, F., Mioc, D., Gold, C.M.: Dynamic Additively Weighted Voronoi Diagrams Made Easy. In: Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG 1998), Montréal, Canada (1998)
Anton, F., Mioc, D., Gold, C.M.: An algorithm for the dynamic construction and maintenance of Additively Weighted Voronoi diagrams. In: Proceedings of the 14th European Workshop on Computational Geometry (CG 1998), Barcelona, Spain, pp. 117–119 (1998)
Anton, F.: Voronoi diagrams of semi-algebraic sets, Ph.D. thesis, The University of British Columbia, Vancouver, British Columbia, Canada (2004)
Aurenhammer, F.: Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16(1), 78–96 (1987)
Aurenhammer, F.: Voronoi diagrams - A survey, Institute for Information Processing, Technical University of Graz, Report 263 (1988)
Beachy, J.A., Blair, W.D.: Abstract Algebra. Waveland Press Inc. (1996)
Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation. Springer, New York (1998) (with a foreword by R.M. Karp)
Berger, M.: Géométrie. espaces euclidiens, triangles, cercles et sphères, CEDIC/FERNAND NATHAN, Paris, vol. 2 (1979)
Boots, B.N.: Some models of random subdivision of space. Geografiska Annaler 55B, 34–48 (1973)
Cox, D., Little, J., O’Shea, D.: Using algebraic geometry. Springer, New York (1998)
Chen, Z., Papadopoulou, E., Xu, J.: Robust algorithm for k-gon voronoi diagram construction. In: Abstracts for the Fourteenth Canadian Conference on Computational Geometry CCCG 2002, Lethbridge, Alberta, Canada, August 2002, pp. 77–81. University of Lethbridge (2002)
Deschamps, A.: Analytical Techniques for Aluminium Alloys. In: Handbook of Aluminum. Alloy Production and Materials manufacturing, vol. 2, pp. 155–192. Marcel Dekker, Inc., New York (2003)
Devillers, O., Meiser, S., Teillaud, M.: Fully Dynamic Delaunay Triangulation in Logarithmic Expected Time per Operation, Rapport INRIA 1349, INRIA, BP93, 06902 Sophia-Antipolis cedex, France (1990)
Emiris, I.Z., Karavelas, M.I.: The predicates of the Apollonius diagram: algorithmic analysis and implementation. Comput. Geom. 33(1-2), 18–57 (2006)
Greuel, G.-M., Pfister, G.: A Singular introduction to commutative algebra. In: Bachmann, O., Lossen, C., Schönemann, H. (eds.), With 1 CD-ROM (Windows, Macintosh, and UNIX). Springer, Berlin (2002)
Grayson, D.R., Stillman, M.E.: Macaulay 2, a software system for research in algebraic geometry, http://www.math.uiuc.edu/Macaulay2/
Guibas, L., Stolfi, J.: Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics 4(2), 74–123 (1985)
Horalek, V.: The Johnson-Mehl tessellation with time dependent nucleation intensity in view of basic 3-D tessellations. Mathematical research 51, 111–116 (1979)
Johnson, W.A., Mehl, F.R.: Reaction kinetics in processes of nucleation and growth. Transactions of the American Institute of Mining, Metallurgical and Petroleum Engineers 135, 416–456 (1939)
Karavelas, M.I., Emiris, I.Z.: Predicates for the Planar Additively Weighted Voronoi Diagram. ECG Technical Report ECG-TR-122201-01, INRIA (2002)
Karavelas, M.I., Emiris, I.Z.: Root comparison techniques applied to computing the additively weighted Voronoi diagram. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, pp. 320–329. ACM, New York (2003)
Kim, D.-S., Kim, D.-U., Sugihara, K.: Voronoi diagram of a circle set constructed from Voronoi diagram of a point set. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol. 1969, pp. 432–443. Springer, Heidelberg (2000)
Kim, D.-S., Kim, D., Sugihara, K.: Voronoi diagram of a circle set from Voronoi diagram of a point set. I. Topology. Comput. Aided Geom. Design 18(6), 541–562 (2001)
Kim, D.-S., Kim, D., Sugihara, K.: Voronoi diagram of a circle set from Voronoi diagram of a point set. II. Geometry. Comput. Aided Geom. Design 18(6), 563–585 (2001)
Klein, R.: Concrete and abstract Voronoï diagrams. Springer, Berlin (1989)
Kolmogorov, A.N.: A statistical theory for the recrystallization of metals. Akad. nauk SSSR, Izv., Ser. Matem. 1(3), 355–359 (1937)
Lang, S.: Algebra, 3rd edn. Graduate Texts in Mathematics, vol. 211. Springer, New York (2002)
Medvedev, N.N.: Voronoi-Delaunay method for non-crystalline structures. SB Russian Academy of Science, Novosibirsk (2000)
Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, Chichester (2001)
Stoyan, D.: Random sets: Models and Statistics. International Statistical Review 66, 1–27 (1998)
Voronoï, G.F.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. premier mémoire. sur quelques propriétés des formes quadratiques positives parfaites. Journal für die reine und angewandte Mathematik 133, 97–178 (1907)
Voronoï, G.F.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. deuxième mémoire. recherches sur les paralléloèdres primitifs. première partie. partition uniforme de l’espace analytique à n dimensions à l’aide des translations d’un même polyèdre convexe. Journal für die reine und angewandte Mathematik 134, 198–287 (1908)
Voronoï, G.F.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. deuxième mémoire. recherches sur les paralléloèdres primitifs. seconde partie. domaines de formes quadratiques correspondant aux différents types de paralléloèdres primitifs. Journal für die reine und angewandte Mathematik 136, 67–181 (1910)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Anton, F., Mioc, D., Gold, C. (2009). The Voronoi Diagram of Circles and Its Application to the Visualization of the Growth of Particles. In: Gavrilova, M.L., Tan, C.J.K. (eds) Transactions on Computational Science III. Lecture Notes in Computer Science, vol 5300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00212-0_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-00212-0_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00211-3
Online ISBN: 978-3-642-00212-0
eBook Packages: Computer ScienceComputer Science (R0)