Abstract Given a locally finite set $$A \subseteq {{\mathbb R}}^d$$ A ⊆ R d and a coloring $$\chi :A \rightarrow \{0,1,\ldots ,s\}$$ χ : A → { 0 , 1 , … , s } , we introduce the chromatic Delaunay mosaic of $$\chi $$ χ , which is a Delaunay mosaic in $${{\mathbb R}}^{d+s}$$ R d + s that represents how points of different colors mingle. Our main results are bounds on the size of the chromatic Delaunay mosaic, in which we assume that d and s are constants. For example, if A is finite with $$n = {{\#}{A}}$$ n = # A , and the coloring is random, then the chromatic Delaunay mosaic has $$O(n^{{\lceil d/2 \rceil }})$$ O ( n ⌈ d / 2 ⌉ ) cells in expectation. In contrast, for Delone sets and Poisson point processes in $${{\mathbb R}}^d$$ R d , the expected number of cells within a closed ball is only a constant times the number of points in this ball. Furthermore, in $${{\mathbb R}}^2$$ R 2 all colorings of a well spread set of n points have chromatic Delaunay mosaics of size O ( n ). This encourages the use of chromatic Delaunay mosaics in applications.

We generalize a classical result by Boris Delaunay that introduced Delaunay triangulations. In particular, we prove that for a locally finite and coarsely dense generic point set A in ℝ^d, every generic point of ℝ^d belongs to exactly binom(d+k,d) simplices whose vertices belong to A and whose circumspheres enclose exactly k points of A. We extend this result to the cases in which the points are weighted, and when A contains only finitely many points in ℝ^d or in 𝕊^d. Furthermore, we use the result to give a new geometric proof for the fact that volumes of hypersimplices are Eulerian numbers.

Grid peeling is the process of repeatedly removing the convex hull vertices of the grid-points that lie inside a given convex curve. It has been conjectured that, for a more and more refined grid, grid peeling converges to a continuous process, the affine curve-shortening flow, which deforms the curve based on the curvature. We prove this conjecture for one class of curves, parabolas with a vertical axis, and we determine the value of the constant factor in the formula that relates the two processes.

Given a finite set, $A \subseteq \mathbb{R}^2$, and a subset, $B \subseteq A$, the \emph{MST-ratio} is the combined length of the minimum spanning trees of $B$ and $A \setminus B$ divided by the length of the minimum spanning tree of $A$. The question of the supremum, over all sets $A$, of the maximum, over all subsets $B$, is related to the Steiner ratio, and we prove this sup-max is between $2.154$ and $2.427$. Restricting ourselves to $2$-dimensional lattices, we prove that the sup-max is $2.0$, while the inf-max is $1.25$. By some margin the most difficult of these results is the upper bound for the inf-max, which we prove by showing that the hexagonal lattice cannot have MST-ratio larger than $1.25$.

Abstract For a locally finite set in $${{{\mathbb {R}}}}^2$$ R 2 , the order-k Brillouin tessellations form an infinite sequence of convex face-to-face tilings of the plane. If the set is coarsely dense and generic, then the corresponding infinite sequences of minimum and maximum angles are both monotonic in k. As an example, a stationary Poisson point process in $${{{\mathbb {R}}}}^2$$ R 2 is locally finite, coarsely dense, and generic with probability one. For such a set, the distributions of angles in the Voronoi tessellations, Delaunay mosaics, and Brillouin tessellations are independent of the order and can be derived from the formula for angles in order-1 Delaunay mosaics given by Miles (Math. Biosci. 6, 85–127 (1970)).

Abstract. For a locally finite set, [Formula: see text], the [Formula: see text] th Brillouin zone of [Formula: see text] is the region of points [Formula: see text] for which [Formula: see text] is the [Formula: see text]th smallest among the Euclidean distances between [Formula: see text] and the points in [Formula: see text]. If [Formula: see text] is a lattice, the [Formula: see text]th Brillouin zones of the points in [Formula: see text] are translates of each other, and together they tile space. Depending on the value of [Formula: see text], they express medium- or long-range order in the set. We study fundamental geometric and combinatorial properties of Brillouin zones, focusing on the integer lattice and its perturbations. Our results include the stability of a Brillouin zone under perturbations, a linear upper bound on the number of chambers in a zone for lattices in [Formula: see text], and the convergence of the maximum volume of a chamber to zero for the integer lattice.

Abstract The Voronoi tessellation in $${{{\mathbb {R}}}}^d$$ R d is defined by locally minimizing the power distance to given weighted points. Symmetrically, the Delaunay mosaic can be defined by locally maximizing the negative power distance to other such points. We prove that the average of the two piecewise quadratic functions is piecewise linear, and that all three functions have the same critical points and values. Discretizing the two piecewise quadratic functions, we get the alpha shapes as sublevel sets of the discrete function on the Delaunay mosaic, and analogous shapes as superlevel sets of the discrete function on the Voronoi tessellation. For the same non-critical value, the corresponding shapes are disjoint, separated by a narrow channel that contains no critical points but the entire level set of the piecewise linear function.

We introduce a network creation game in which each player (vertex) has a fixed budget to establish links to other players. In this model, each link has a unit price, and each agent tries to minimize its cost, which is either its eccentricity or its total distance to other players in the underlying (undirected) graph of the created network. Two versions of the game are studied: In the MAX version, the cost incurred to a vertex is the maximum distance between the vertex and other vertices, and, in the SUM version, the cost incurred to a vertex is the sum of distances between the vertex and other vertices. We prove that in both versions pure Nash equilibria exist, but the problem of finding the best response of a vertex is NP-hard. We take the social cost of the created network to be its diameter, and next we study the maximum possible diameter of an equilibrium graph with n vertices in various cases. When the sum of players’ budgets is n − 1, the equilibrium graphs are always trees, and we prove that their maximum diameter is Θ( n ) and Θ(log n ) in MAX and SUM versions, respectively. When each vertex has a unit budget (i.e., can establish a link to just one vertex), the diameter of any equilibrium graph in either version is Θ(1). We give examples of equilibrium graphs in the MAX version, such that all vertices have positive budgets and yet the diameter is Ω(√log n ). This interesting (and perhaps counterintuitive) result shows that increasing the budgets may increase the diameter of equilibrium graphs and hence deteriorate the network structure. Then we prove that every equilibrium graph in the SUM version has diameter 2 O (√log n ) . Finally, we show that if the budget of each player is at least k , then every equilibrium graph in the SUM version is k -connected or has a diameter smaller than 4.

We consider a network creation game in which, each player (vertex) has a limited budget to establish links to other players. In our model, each link has a unit cost and each agent tries to minimize its cost which is its local diameter or its total distance to other players in the (undirected) underlying graph of the created network. Two variants of the game are studied: in the MAX version, the cost incurred to a vertex is the maximum distance between that vertex and other vertices, and in the SUM version, the cost incurred to a vertex is the sum of distances between that vertex and other vertices. We prove that in both versions pure Nash equilibria exist, but the problem of finding the best response of a vertex is NP-hard.