Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functions that facilitates the efficient search for new materials and material properties. We prove invariance under isometries, continuity, and completeness i
n the generic case, which are necessary features for the reliable comparison of crystals. The proof of continuity integrates methods from discrete geometry and lattice theory, while the proof of generic completeness combines techniques from geometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and related inclusion-exclusion formulae. We have implemented the algorithm and describe its application to crystal structure prediction.
Generalizing the decomposition of a connected planar graph into a tree and a dual tree, we prove a combinatorial analog of the classic Helmholz-Hodge decomposition of a smooth vector field. Specifically, we show that for every polyhedral complex, $K$
, and every dimension, $p$, there is a partition of the set of $p$-cells into a maximal $p$-tree, a maximal $p$-cotree, and a collection of $p$-cells whose cardinality is the $p$-th Betti number of $K$. Given an ordering of the $p$-cells, this tri-partition is unique, and it can be computed by a matrix reduction algorithm that also constructs canonical bases of cycle and boundary groups.
The approximation of a circle with a fine square grid distorts the perimeter by a factor of $tfrac{4}{pi}$. We prove that this factor is the same on average for approximations of any curve with any Delaunay mosaic (known as Voronoi path), and extend
the results to all dimensions, generalizing Voronoi paths to Voronoi scapes.
We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order-$k$ mosaic from incrementally constructed lower-order mosaics and uses
an algorithm for weighted first-order Delaunay mosaics as a black-box to construct the order-$k$ mosaic from its vertices. Beyond this black-box, the algorithm uses only combinatorial operations, thus facilitating easy implementation. We extend this algorithm to compute higher-order $alpha$-shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.
Consider a random set of points on the unit sphere in $mathbb{R}^d$, which can be either uniformly sampled or a Poisson point process. Its convex hull is a random inscribed polytope, whose boundary approximates the sphere. We focus on the case $d=3$,
for which there are elementary proofs and fascinating formulas for metric properties. In particular, we study the fraction of acute facets, the expected intrinsic volumes, the total edge length, and the distance to a fixed point. Finally we generalize the results to the ellipsoid with homeoid density.
Representing an atom by a solid sphere in $3$-dimensional Euclidean space, we get the space-filling diagram of a molecule by taking the union. Molecular dynamics simulates its motion subject to bonds and other forces, including the solvation free ene
rgy. The morphometric approach [HRC13,RHK06] writes the latter as a linear combination of weight
The morphometric approach [HRC13,RHK06] writes the solvation free energy as a linear combination of weight
Among other results, we prove the following theorem about Steiner minimal trees in $d$-dimensional Euclidean space: if two finite sets in $mathbb{R}^d$ have unique and combinatorially equivalent Steiner minimal trees, then there is a homotopy between
the two sets that maintains the uniqueness and the combinatorial structure of the Steiner minimal tree throughout the homotopy.
Various kinds of data are routinely represented as discrete probability distributions. Examples include text documents summarized by histograms of word occurrences and images represented as histograms of oriented gradients. Viewing a discrete probabi
lity distribution as a point in the standard simplex of the appropriate dimension, we can understand collections of such objects in geometric and topological terms. Importantly, instead of using the standard Euclidean distance, we look into dissimilarity measures with information-theoretic justification, and we develop the theory needed for applying topological data analysis in this setting. In doing so, we emphasize constructions that enable usage of existing computational topology software in this context.
The order-$k$ Voronoi tessellation of a locally finite set $X subseteq mathbb{R}^n$ decomposes $mathbb{R}^n$ into convex domains whose points have the same $k$ nearest neighbors in $X$. Assuming $X$ is a stationary Poisson point process, we give expl
icit 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.
