Expectation of random polytopes

A random polytopeP _n in a convex bodyC is the convex hull ofn identically and independently distributed points inC. Its expectation is a convex body in the interior ofC. We study the deviation of the expectation ofP _n fromC asn→∞: while forC of classC ^k+1,k≥1, precise asymptotic expansions for the deviation exist, the behaviour of the deviation is extremely irregular for most convex bodiesC of classC ¹. Dedicated to my teacher and friend Professor Edmund Hlawka on the occasion of his 80^th birthday     

Volumes of symmetric random polytopes

We consider the moments of the volume of the symmetric convex hull of independent random points in an n-dimensional symmetric convex body. We calculate explicitly the second and fourth moments for n points when the given body is (and all of the moments for the case q = 2), and derive from these the asymptotic behavior, as , of the expected volume of a random simplex in those bodies. Received: 5 February 2003     

Rotational integral geometry of tensor valuations

We derive a new rotational Crofton formula for Minkowski tensors. In special cases, this formula gives (1) the rotational average of Minkowski tensors defined on linear subspaces and (2) the functional defined on linear subspaces with rotational average equal to a Minkowski tensor. Earlier results obtained for intrinsic volumes appear now as special cases.     

Packing random intervals

Summary Letn random intervalsI ₁, ...,I _n be chosen by selecting endpoints independently from the uniform distribution on [0.1]. Apacking is a pairwise disjoint subset of the intervals; itswasted space is the Lebesgue measure of the points of [0,1] not covered by the packing. In any set of intervals the packing with least wasted space is computationally easy to find; but its expected wasted space in the random case is not obvious. We show that with high probability for largen, this best packing has wasted space . It turns out that if the endpoints 0 and 1 are identified, so that the problem is now one of packing random arcs in a unit-circumference circle, then optimal wasted space is reduced toO(1/n). Interestingly, there is a striking difference between thesizes of the best packings: about logn intervals in the unit interval case, but usually only one or two arcs in the circle case.     

Polynomial parallel volume, convexity and contact distributions of random sets

We characterize convexity of a random compact set X in ℝ^d via polynomial expected parallel volume of X. The parallel volume of a compact set A is a function of r≥0 and is defined here in two steps. First we form the parallel set at distance r with respect to a one- or two-dimensional gauge body B. Then we integrate the volume of this (relative) parallel set with respect to all rotations of B. We apply our results to characterize convexity of the typical grain of a Boolean model via first contact distributions.     

Inside-out polytopes

We present a common generalization of counting lattice points in rational polytopes and the enumeration of proper graph colorings, nowhere-zero flows on graphs, magic squares and graphs, antimagic squares and graphs, compositions of an integer whose parts are partially distinct, and generalized latin squares. Our method is to generalize Ehrhart's theory of lattice-point counting to a convex polytope dissected by a hyperplane arrangement. We particularly develop the applications to graph and signed-graph coloring, compositions of an integer, and antimagic labellings.     

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.     

Component structure in the evolution of random hypergraphs

The component structure of the most general random hypergraphs, with edges of differen sizes, is analyzed. We show that, as this is the case for random graphs, there is a “double jump” in the probable and almost sure size of the greatest component of hypergraphs, when the average vertex degree passes the value 1.     

Expected intrinsic volumes and facet numbers of random beta‐polytopes

Let be i.i.d. random points in the d‐dimensional Euclidean space sampled according to one of the following probability densities: and We compute exactly the expected intrinsic volumes and the expected number of facets of the convex hull of . Asymptotic formulae were obtained previously by Affentranger [The convex hull of random points with spherically symmetric distributions, 1991]. By studying the limits of the beta case when , respectively , we can also cover the models in which are uniformly distributed on the unit sphere or normally distributed, respectively. We obtain similar results for the random polytopes defined as the convex hulls of and . One of the main tools used in the proofs is the Blaschke–Petkantschin formula.     

k-sets and random hulls

We re-examine the probabilistic analysis of Clarkson and Shor [5] involvingk-sets of point sets and related structures. By studying more carefully the equations that they derive, we are able to obtain refined analysis of these quantities, which lead to a collection of interesting relationships involvingk-sets, convex hulls of random samples, and generalizations of these constructs.Work on this paper has been supported by Office of Naval Research Grant N00014-89-J-3042 and N00014-90-J-1284, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Processes of flats induced by higher dimensional processes III

Stationary processes of k-flats in ^d can be thought of as point processes on the Grassmannian _k ^d of k-dimensional subspaces of ^d . If such a process is sampled by a (d–k+ j)-dimensional space F, it induces a process of j-flats in F. In this work we will investigate the possibility of determining the original k-process from knowledge of the intensity measures of the induced j-processes. We will see that this is impossible precisely when 1<k<d–1 and j=0,...,2[r/2]–1, where r is the rank of the manifold _k ^d . We will show how the problem is equivalent to the study of the kernel of various integral transforms, these will then be investigated using harmonic analysis on Grassmannian manifolds.The research of the first and third authors was supported in part by NSF grants DMS-9207019 and DMS-9304284. The research of the second author was supported in part by NFR contract number R-RA 4873-306 and the Swedish Academy of Sciences.     

Mixed curvature measures for sets of positive reach and a translative integral formula

Mixed curvature measures for sets of positive reach are introduced and a translative version of the principal kinematic formula from integral geometry is proved. This is an extension of a known result from convex geometry. Integral representations of the mixed curvature measures in various particular cases of dimension two and three are derived.     

Integral geometry and geometric inequalities in hyperbolic space

Using results from integral geometry, we find inequalities involving mean curvature integrals of convex hypersurfaces in hyperbolic space. Such inequalities generalize the Minkowski formulas for euclidean convex sets.     

Fractal penrose tiles II: Tiles with fractal boundary as duals of penrose triangles

Summary Suppose given a quasi-periodic tiling of some Euclidean space E _u which is self-similar under the linear expansiong: E_μ→E_μ. It is known that there is an embedding of E_μ into some higher-dimensional space ℝ ^N and a linear automorphism with integer coefficients such that E _u ⊂ ℝ ^N is invariant under andg is the restriction of to E _u . Let E _s be the -invariant complement of E _u , and . If certain conditions are fulfilled (e.g. must be a lattice automorphism,g ^* is an expansion), we construct a self-similar tiling of E _s whose expansion isg ^*, using the information contained in the original tiling of E_μ. The term “Galois duality” of tilings is motivated by the fact that the eigenvalues ofg ^* are Galois conjugates of those ofg. Our method can be applied to find the Galois duals which are given by Thurston, obtained in a somewhat other way for the case that dim E_μ=1, andg is the multiplication by a cubic Pisot unit. Bandt and Gummelt have found fractally shaped tilings which can be considered as strictly self-similar modifications of the kites-and-darts, and the rhombi tilings of Penrose. As one of the examples, we show that these fractal versions can be constructed by dualizing tilings by Penrose triangles.     

On tile-k-transitive tilings of the space

General methods for finding tile-k-transitive tilings of the three-dimensional Euclidean space with polyhedral bodies are discussed. Analogous methods for enumerating k-isohedral tilings of a two-dimensional plane of constant curvature have been obtained previously.     

Point processes of cylinders,particles and flats

Point processesX of cylinders, compact sets (particles), or flats inR ^d are mathematical models for fields of sets as they occur, e.g., in practical problems of image analysis and stereology. For the estimation of geometric quantities of such fields, mean value formulas forX are important. By a systematic approach, integral geometric formulas for curvature measures are transformed into density formulas for geometric point processes. In particular, a number of results which are known for stationary and isotropic Poisson processes of convex sets are generalized to nonisotropic processes, to non-Poissonian processes, and to processes of nonconvex sets. The integral geometric background (including recent results from translative integral geometry), the fundamentals of geometric point processes, and the resulting density formulas are presented in detail. Generalizations of the theory and applications in image analysis and stereology are mentioned shortly.     

Farthest points and cut loci on some degenerate convex surfaces

We study farthest points and cut loci on doubly covered convex polygons, and determine them explicitly on doubly covered n-dimensional simplices.     

Clifford-algebraic random walks on the hypercube

The n-dimensional hypercube is a simple graph on 2ⁿ vertices labeled by binary strings, or words, of length n. Pairs of vertices are adjacent if and only if they differ in exactly one position as binary words; i.e., the Hamming distance between the words is one. A discrete-time random walk is easily defined on the hypercube by “flipping” a randomly selected digit from 0 to 1 or vice-versa at each time step. By associating the words as blades in a Clifford algebra of particular signature, combinatorial properties of the geometric product can be used to represent this random walk as a sequence within the algebra. A closed-form formula is revealed which yields probability distributions on the vertices of the hypercube at any time k ≥ 0 by a formal power series expansion of elements in the algebra. Furthermore, by inducing a walk on a larger Clifford algebra, probabilities of self-avoiding walks and expected first hitting times of specific vertices are recovered. Moreover, because the Clifford algebras used in the current work are canonically isomorphic to fermion algebras, everything appearing here can be rewritten using fermion creation/annihilation operators, making the discussion relevant to quantum mechanics and/or quantum computing.