Exploratory data analysis for planar tessellations: Structural analysis and point process methods

This paper presents methods for the exploratory analysis of particular geometrical data, namely planar tessellations. At first, two non-stochastic methods are suggested which may help to classify tessellations and to understand their structure. The first one consists of approximating a given tessellation by a Dirichlet tessellation. The other one uses the nodes of a given tessellation and tests the possibility of reconstructing it by a fixed rule of connecting nodes by edges. Furthermore, in order to obtain information on the spatial behaviour of a tessellation, we suggest the use of the methods of point process statistics. In particular, pair correlation and mark correlation functions describe spatial correlations in tessellations.     

The Combinatorial Structure of Spatial STIT Tessellations

Spatially homogeneous random tessellations that are stable under iteration (nesting) in the $3$ 3 -dimensional Euclidean space are considered, so-called STIT tessellations. They arise as outcome of a space-time process of subsequent cell division and, consequently, they are not facet-to-facet. The intent of this paper is to develop a detailed analysis of the combinatorial structure of such tessellations and to determine a number of new geometric mean values, for example for the neighbourhood of the typical vertex. The heart of the results is a fine classification of tessellation edges based on the type of their endpoints or on the equality relationship with other types of line segments. In the background of the proofs are delicate distributional properties of spatial STIT tessellations.     

Bernoulli Cluster Field: Voronoi Tessellations

A new point process is proposed which can be viewed either as a Boolean cluster model with two cluster modes or as a p-thinned Neyman-Scott cluster process with the retention of the original parent point. Voronoi tessellation generated by such a point process has extremely high coefficients of variation of cell volumes as well as of profile areas and lengths in the planar and line induced tessellations. An approximate numerical model of tessellation characteristics is developed for the case of small cluster size; its predictions are compared with the results of computer simulations. Tessellations of this type can be used as models of grain structures in steels.     

Second-Order Characteristics of the Edge System of Random Tessellations and the PPI Value of Foams

The mean number of pores per inch (PPI) is widely used as a pore size characteristic for foams. Nevertheless, there is still a lack of fast and reliable methods for estimating this quantity. We propose a method for estimating the PPI value based on the Bartlett spectrum of a dark field image of the material. To this end, second-order properties of the edge systems of random tessellations are investigated in detail. In particular, we study the spectral density of the random length measure of the edges. It turns out that the location of its first local maximum is proportional to the PPI value. To determine the factor of proportionality, several random tessellation models as well as examples of real foams are investigated. To mimic the image acquisition process, 2D sections and projections of 3D tessellations are considered.     

Distributional properties of the typical cell of stationary iterated tessellations

Distributional properties are considered of the typical cell of stationary iterated tessellations (SIT), which are generated by stationary Poisson-Voronoi tessellations (SPVT) and stationary Poisson line tessellations (SPLT), respectively. Using Neveus exchange formula, the typical cell of SIT can be represented by those cells of its component tessellation hitting the typical cell of its initial tessellation. This provides a simulation algorithm without consideration of limits in space. It has been applied in order to estimate the probability densities of geometric characteristics of the typical cell of SIT generated by SPVT and SPLT. In particular, the probability densities of the number of vertices, the perimeter, and the area of the typical cell of such SIT have been determined.Acknowledgement. This work was supported by France Telecom R&D through research grant no. 001B130.     

A global construction of homogeneous random planar tessellations that are stable under iteration

Homogeneous (i.e. spatially stationary) random tessellations of the Euclidean plane are constructed which have the characteristic property to be stable under the operation of iteration (or nesting), STIT for short. It is based on a Poisson point process on the space of lines that are endowed with a time of birth. A new approach is presented that describes the tessellation in the whole plane. So far, an explicit geometrical construction for those tessellations was only known within bounded windows.     

Asymptotics for Statistical Distances Based on Voronoi Tessellations

We obtain an information-type inequality and a strong law for a wide class of statistical distances between empirical estimates and random measures based on Voronoi tessellations. This extends some basic results in the asymptotic theory of sample spacings, when the cells of the Voronoi tessellation are interpreted as d-dimensional spacings.     

Poisson polyhedra in high dimensions

The zero cell of a parametric class of random hyperplane tessellations depending on a distance exponent and an intensity parameter is investigated, as the space dimension tends to infinity. The model includes the zero cell of stationary and isotropic Poisson hyperplane tessellations as well as the typical cell of a stationary Poisson Voronoi tessellation as special cases. It is shown that asymptotically in the space dimension, with overwhelming probability these cells satisfy the hyperplane conjecture, if the distance exponent and the intensity parameter are suitably chosen dimension-dependent functions. Also the high dimensional limits of the mean number of faces are explored and the asymptotic behaviour of an isoperimetric ratio is analysed. In the background are new identities linking the f-vector of the zero cell to certain dual intrinsic volumes.     

How many T‐tessellations on k lines? Existence of associated Gibbs measures on bounded convex domains

The paper bounds the number of tessellations with T‐shaped vertices on a fixed set of k lines: tessellations are efficiently encoded, and algorithms retrieve them, proving injectivity. This yields existence of a completely random T‐tessellation, as defined by Kiêu et al. (Spat Stat 6 (2013) 118–138), and of its Gibbsian modifications. The combinatorial bound is sharp, but likely pessimistic in typical cases. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 561–587, 2015     

The Poisson Voronoi Tessellation II. Edge Length Distribution Functions

This paper presents a method for the determination of the distribution function of the length of the 'typical' edge of the Poisson Voronoi tessellation. The method is based on distributional properties of the configuration of the centres in the neighbourhood of the 'typical' vertex. The distribution and density functions of the edge lengths are given in double integral form for various dimensions. Analogous characteristics are considered for two-dimensional sections through higher-dimensional Poisson Voronoi tessellations.     

Step length problem for trimming curve approximation in tessellating trimmed surfaces

A trimmed parametric surface is mainly composed of a surface together with trimming curves lying in D, the parametric space of the surface. By investigating the interrelation between surface tessellation and trimming curve approximation, we point out some problems on trimming curve approximation in existing trimmed surface tessellation algorithms. Counter examples are presented to show that a valid approximation of trimming curves in D together with the refinement imposed by surface tessellation does not necessarily generate a valid linear approximation in 3D space. To assure the 3D derivation tolerance, we propose two novel step-length estimation methods such that a piecewise linear interpolant of the trimming curve based on the proposed step lengths will result in a valid linear approximation in 3D space. The first method exploits the triangle inequality and takes the derivation tolerance in 3D space into account to compute the effective step length. Our second method is based on segmenting the trimming curve into subcurves first and then approximates each subcurve according to the derivation tolerance in 3D space. Moreover, several empirical tests are given to demonstrate the correctness of our step length estimations.     

2D Centroidal Voronoi Tessellations with Constraints

<正>We tackle the problem of constructing 2D centroidal Voronoi tessellations with constraints through an efficient and robust construction of bounded Voronoi diagrams, the pseudo-dual of the constrained Delaunay triangulation.We exploit the fact that the cells of the bounded Voronoi diagram can be obtained by clipping the ordinary ones against the constrained Delaunay edges.The clipping itself is efficiently computed by identifying for each constrained edge the(connected) set of triangles whose dual Voronoi vertices are hidden by the constraint.The resulting construction is amenable to Lloyd relaxation so as to obtain a centroidal tessellation with constraints.     

Simulation of typical Cox–Voronoi cells with a special regard to implementation tests

We consider stationary Poisson line processes in the Euclidean plane and analyze properties of Voronoi tessellations induced by Poisson point processes on these lines. In particular, we describe and test an algorithm for the simulation of typical cells of this class of Cox–Voronoi tessellations. Using random testing, we validate our algorithm by comparing theoretical values of functionals of the zero cell to simulated values obtained by our algorithm. Finally, we analyze geometric properties of the typical Cox–Voronoi cell and compare them to properties of the typical cell of other well-known classes of tessellations, especially Poisson–Voronoi tessellations. Our results can be applied to stochastic–geometric modelling of networks in telecommunication and life sciences, for example. The lines can then represent roads in urban road systems, blood arteries or filament structures in biological tissues or cells, while the points can be locations of telecommunication equipment or vesicles, respectively.     

Model Based Estimation of Geometric Characteristics of Open Foams

Open cell foams are a class of modern materials which is interesting for a wide variety of applications and which is not accessible to classical materialography based on 2d images. 3d imaging by micro computed tomography is a practicable alternative. Analysis of the resulting volume images is either based on a simple binarisation of the image or on so-called cell reconstruction by image processing. The first approach allows to estimate mean characteristics like the mean cell volume using the typical cell of a random spatial tessellation as model for the cell shape. The cell reconstruction allows estimation of empirical distributions of cell characteristics. This paper summarises the theoretical background for the first method, in particular estimation of the intrinsic volumes and their densities from discretized data and models for random spatial tessellations. The accuracy of the estimation method is assessed using the dilated edge systems of simulated random spatial tessellations.     

Elliptic operators on planar graphs: Unique continuation for eigenfunctions and nonpositive curvature

This paper is concerned with elliptic operators on plane tessellations. We show that such an operator does not admit a compactly supported eigenfunction if the combinatorial curvature of the tessellation is nonpositive. Furthermore, we show that the only geometrically finite, repetitive plane tessellations with nonpositive curvature are the regular and tilings.

     

Representation complexity of adaptive 3D distance fields

In this paper we study the representation complexity of a kind of data structure that stores the information necessary to compute the distance from a point to a geometric body. These data structures called adaptive splitting based on cubature distance fields (ASBCDF), are binary search trees generated by the adaptive splitting based on cubature (ASBC) algorithm that adaptively subdivides the space surrounding the body into tetrahedra. Their representation complexity is measured by the number of nodes in the tree (two times the number of tetrahedra in the resulting tessellation). In the case of convex polyhedra we prove that this quantity remains bounded as the number of vertices of the polyhedra increases to infinity. Experimental results show that the number of tetrahedra in the tessellations is almost independent of the combinatorial complexity of the polyhedra. This means that the average compute time of the distance to arbitrary convex polyhedra is almost constant. Therefore, ASBCDFs are especially suitable for real time applications involving rapidly changing environments modelized with complex polyhedra.     

Extremal properties of some geometric processes

In this paper some isoperimetric inequalities for stationary random tessellations are discussed. At first, classical results on deterministic tessellations in the Euclidean plane are extended to the case of random tessellations. An isoperimetric inequality for the random Poisson polygon is derived as a consequence of a theorem of Davidson concerning an extremal property of tessellations generated by random lines inR ². We mention extremal properties of stationary hyperplane tessellations inR ^d related to Davidson's result in cased=2. Finally, similar problems for random arrangements ofr-flats inR ^d are considered (r).This work was done while the author was visiting the University of Strathclyde in Glasgow.     

Shape-driven nested Markov tessellations

A new and rather broad class of stationary random tessellations of the d-dimensional Euclidean space is introduced, which we call shape-driven nested Markov tessellations. Locally, these tessellations are constructed by means of a spatio-temporal random recursive split dynamics governed by a family of Markovian split kernel, generalizing thereby the – by now classical – construction of iteration stable random tessellations. By providing an explicit global construction of the tessellations, it is shown that under suitable assumptions on the split kernels (shape-driven), there exists a unique time-consistent whole-space tessellation-valued Markov process of stationary random tessellations compatible with the given split kernels. Beside the existence and uniqueness result, the typical cell and some aspects of the first-order geometry of these tessellations are in the focus of our discussion.     

The Poisson Voronoi Tessellation III. Miles' Formula

This paper gives distributional properties of geometrical characteristics of a Voronoi tessellation generated by a stationary Poisson point process. The considerations are based on a well-known formula given by [10] describing size and shape of a cell of the Delaunay tessellation and on the close connection between Delaunay and Voronoi tessellation. Several results are given for the two-dimensional case, but the main part is the investigation of the three-dimensional case. They include the density functions of the angles perpendicular to the ‘typical’ edge, spanned by two neighbouring Poisson points and that spanned by two neighbouring faces, the angle between two edges emanating from the ‘typical’ vertex, the distance of two neighbouring Poisson points, the angle between two edges emanating from the ‘typical’ vertex of the Poisson Voronoi tessellation and some others. These density functions are given partly explicitely and partly in integral form.     

Moyennes empiriques pour les mosaïques de Voronoi du disque de Poincaré

Let Φ be a stationary ergodic point process with finite intensity of the Poincaré disk. After defining the typical cell associated to the Voronoi tessellation of Φ, we study the convergence of empirical means of this tessellation. Contrary to the Euclidean case, several natural choices of means exist, leading to different behavior. The case where Φ is a Poisson process is more specifically characterized. To cite this article: F. Lips, C. R. Acad. Sci. Paris, Ser. I 342 (2006).