TY - JOUR
AB - Slicing a Voronoi tessellation in ${R}^n$ with a $k$-plane gives a $k$-dimensional weighted Voronoi tessellation, also known as a power diagram or Laguerre tessellation. Mapping every simplex of the dual weighted Delaunay mosaic to the radius of the smallest empty circumscribed sphere whose center lies in the $k$-plane gives a generalized discrete Morse function. Assuming the Voronoi tessellation is generated by a Poisson point process in ${R}^n$, we study the expected number of simplices in the $k$-dimensional weighted Delaunay mosaic as well as the expected number of intervals of the Morse function, both as functions of a radius threshold. As a by-product, we obtain a new proof for the expected number of connected components (clumps) in a line section of a circular Boolean model in ${R}^n$.
AU - Edelsbrunner, Herbert
AU - Nikitenko, Anton
ID - 7554
IS - 4
JF - Theory of Probability and its Applications
SN - 0040585X
TI - Weighted Poisson–Delaunay mosaics
VL - 64
ER -
TY - CONF
AB - Discrete Morse theory has recently lead to new developments in the theory of random geometric complexes. This article surveys the methods and results obtained with this new approach, and discusses some of its shortcomings. It uses simulations to illustrate the results and to form conjectures, getting numerical estimates for combinatorial, topological, and geometric properties of weighted and unweighted Delaunay mosaics, their dual Voronoi tessellations, and the Alpha and Wrap complexes contained in the mosaics.
AU - Edelsbrunner, Herbert
AU - Nikitenko, Anton
AU - Ölsböck, Katharina
AU - Synak, Peter
ID - 8135
SN - 21932808
T2 - Topological Data Analysis
TI - Radius functions on Poisson–Delaunay mosaics and related complexes experimentally
VL - 15
ER -
TY - JOUR
AB - The order-k Voronoi tessellation of a locally finite set 𝑋⊆ℝ𝑛 decomposes ℝ𝑛 into convex domains whose points have the same k nearest neighbors in X. Assuming X is a stationary Poisson point process, we give explicit formulas for the expected number and total area of faces of a given dimension per unit volume of space. We also develop a relaxed version of discrete Morse theory and generalize by counting only faces, for which the k nearest points in X are within a given distance threshold.
AU - Edelsbrunner, Herbert
AU - Nikitenko, Anton
ID - 5678
IS - 4
JF - Discrete and Computational Geometry
SN - 01795376
TI - Poisson–Delaunay Mosaics of Order k
VL - 62
ER -
TY - JOUR
AB - Using the geodesic distance on the n-dimensional sphere, we study the expected radius function of the Delaunay mosaic of a random set of points. Specifically, we consider the partition of the mosaic into intervals of the radius function and determine the expected number of intervals whose radii are less than or equal to a given threshold. We find that the expectations are essentially the same as for the Poisson–Delaunay mosaic in n-dimensional Euclidean space. Assuming the points are not contained in a hemisphere, the Delaunay mosaic is isomorphic to the boundary complex of the convex hull in Rn+1, so we also get the expected number of faces of a random inscribed polytope. As proved in Antonelli et al. [Adv. in Appl. Probab. 9–12 (1977–1980)], an orthant section of the n-sphere is isometric to the standard n-simplex equipped with the Fisher information metric. It follows that the latter space has similar stochastic properties as the n-dimensional Euclidean space. Our results are therefore relevant in information geometry and in population genetics.
AU - Edelsbrunner, Herbert
AU - Nikitenko, Anton
ID - 87
IS - 5
JF - Annals of Applied Probability
TI - Random inscribed polytopes have similar radius functions as Poisson-Delaunay mosaics
VL - 28
ER -
TY - JOUR
AB - Mapping every simplex in the Delaunay mosaic of a discrete point set to the radius of the smallest empty circumsphere gives a generalized discrete Morse function. Choosing the points from a Poisson point process in ℝ n , we study the expected number of simplices in the Delaunay mosaic as well as the expected number of critical simplices and nonsingular intervals in the corresponding generalized discrete gradient. Observing connections with other probabilistic models, we obtain precise expressions for the expected numbers in low dimensions. In particular, we obtain the expected numbers of simplices in the Poisson–Delaunay mosaic in dimensions n ≤ 4.
AU - Edelsbrunner, Herbert
AU - Nikitenko, Anton
AU - Reitzner, Matthias
ID - 718
IS - 3
JF - Advances in Applied Probability
SN - 00018678
TI - Expected sizes of poisson Delaunay mosaics and their discrete Morse functions
VL - 49
ER -
TY - THES
AB - The main objects considered in the present work are simplicial and CW-complexes with vertices forming a random point cloud. In particular, we consider a Poisson point process in R^n and study Delaunay and Voronoi complexes of the first and higher orders and weighted Delaunay complexes obtained as sections of Delaunay complexes, as well as the Čech complex. Further, we examine theDelaunay complex of a Poisson point process on the sphere S^n, as well as of a uniform point cloud, which is equivalent to the convex hull, providing a connection to the theory of random polytopes. Each of the complexes in question can be endowed with a radius function, which maps its cells to the radii of appropriately chosen circumspheres, called the radius of the cell. Applying and developing discrete Morse theory for these functions, joining it together with probabilistic and sometimes analytic machinery, and developing several integral geometric tools, we aim at getting the distributions of circumradii of typical cells. For all considered complexes, we are able to generalize and obtain up to constants the distribution of radii of typical intervals of all types. In low dimensions the constants can be computed explicitly, thus providing the explicit expressions for the expected numbers of cells. In particular, it allows to find the expected density of simplices of every dimension for a Poisson point process in R^4, whereas the result for R^3 was known already in 1970's.
AU - Nikitenko, Anton
ID - 6287
TI - Discrete Morse theory for random complexes
ER -
TY - JOUR
AB - We introduce the Voronoi functional of a triangulation of a finite set of points in the Euclidean plane and prove that among all geometric triangulations of the point set, the Delaunay triangulation maximizes the functional. This result neither extends to topological triangulations in the plane nor to geometric triangulations in three and higher dimensions.
AU - Edelsbrunner, Herbert
AU - Glazyrin, Alexey
AU - Musin, Oleg
AU - Nikitenko, Anton
ID - 1173
IS - 5
JF - Combinatorica
SN - 02099683
TI - The Voronoi functional is maximized by the Delaunay triangulation in the plane
VL - 37
ER -
TY - JOUR
AB - We consider packings of congruent circles on a square flat torus, i.e., periodic (w.r.t. a square lattice) planar circle packings, with the maximal circle radius. This problem is interesting due to a practical reason—the problem of “super resolution of images.” We have found optimal arrangements for N=6, 7 and 8 circles. Surprisingly, for the case N=7 there are three different optimal arrangements. Our proof is based on a computer enumeration of toroidal irreducible contact graphs.
AU - Musin, Oleg
AU - Nikitenko, Anton
ID - 1222
IS - 1
JF - Discrete & Computational Geometry
TI - Optimal packings of congruent circles on a square flat torus
VL - 55
ER -