Converting Tessellations into Graphs: From Voronoi Tessellations to Complete Graphs

Abstract

A mathematical procedure enabling the transformation of an arbitrary tessellation of a surface into a bi-colored, complete graph is introduced. Polygons constituting the tessellation are represented by vertices of the graphs. Vertices of the graphs are connected by two kinds of links/edges, namely, by a green link, when polygons have the same number of sides, and by a red link, when the polygons have a different number of sides. This procedure gives rise to a semi-transitive, complete, bi-colored Ramsey graph. The Ramsey semi-transitive number was established as Rtrans(3,3)=5 Shannon entropies of the tessellation and graphs are introduced. Ramsey graphs emerging from random Voronoi and Poisson Line tessellations were investigated. The limits ζ=limN→∞NgNr, where N is the total number of green and red seeds, Ng and Nr, were found ζ= 0.272 ± 0.001 (Voronoi) and ζ= 0.47 ± 0.02 (Poisson Line). The Shannon Entropy for the random Voronoi tessellation was calculated as S= 1.690 ± 0.001 and for the Poisson line tessellation as S = 1.265 ± 0.015. The main contribution of the paper is the calculation of the Shannon entropy of the random point process and the establishment of the new bi-colored Ramsey graph on top of the tessellations.

Keywords

• tessellation
• graph
• Ramsey theory
• transitivity
• Voronoi tessellation
• random Voronoi diagram