
==== Front
J Appl Comput Topol
J Appl Comput Topol
Journal of Applied and Computational Topology
2367-1726
2367-1734
Springer International Publishing Cham

173
10.1007/s41468-024-00173-w
Article
Depth in arrangements: Dehn–Sommerville–Euler relations with applications
https://orcid.org/0000-0002-5372-7890
Biswas Ranita
https://orcid.org/0000-0001-6249-0832
Cultrera di Montesano Sebastiano sebastiano.cultrera@ist.ac.at

https://orcid.org/0000-0002-9823-6833
Edelsbrunner Herbert
https://orcid.org/0000-0002-4201-5775
Saghafian Morteza
grid.33565.36 0000000404312247 IST Austria (Institute of Science and Technology Austria), Klosterneuburg, Austria
3 5 2024
3 5 2024
2024
8 3 557578
26 7 2022
19 3 2024
26 3 2024
© The Author(s) 2024
2024
https://creativecommons.org/licenses/by/4.0/ Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
The depth of a cell in an arrangement of n (non-vertical) great-spheres in Sd is the number of great-spheres that pass above the cell. We prove Euler-type relations, which imply extensions of the classic Dehn–Sommerville relations for convex polytopes to sublevel sets of the depth function, and we use the relations to extend the expressions for the number of faces of neighborly polytopes to the number of cells of levels in neighborly arrangements.

Keywords

Arrangements of great-spheres
Euler characteristics
Dehn–Sommerville relations
Discrete Morse theory
Neighborly polytopes
Counting
Mathematics Subject Classification

Theory of computation
Computational geometry
http://dx.doi.org/10.13039/100010663 H2020 European Research Council 788183 Edelsbrunner Herbert http://dx.doi.org/10.13039/501100002428 Austrian Science Fund Z 342-N31 I 02979-N35 Edelsbrunner Herbert Institute of Science and Technology (IST Austria)Open access funding provided by Institute of Science and Technology (IST Austria).

issue-copyright-statement© Springer Nature Switzerland AG 2024
==== Body
pmcIntroduction

The use of topological methods to study questions in discrete geometry is a well established paradigm, as documented in survey articles (Björner 1995; Živaljević 2017) and books (Matoušek 2008). This paper contributes by viewing questions about splitting finite point sets through the lens of the discrete depth function defined on a corresponding arrangement. To avoid the case analysis needed to distinguish bounded and unbounded cells, we work with arrangements of great-spheres on Sd rather than of hyperplanes in Rd. Assuming non-vertical great-spheres (which do not pass through the north-pole and the south-pole) the depth function maps every cell of the arrangement to the number of great-spheres that separate the cell from the north-pole.

Aspects of this function have been studied in the past, such as the maximum number of chambers (top-dimensional cells) at a given depth, which relates to counting k-sets in a set of n points, which are subsets of k points that can be separated from the remaining n-k points by a straight line; see e.g. Erdős et al. (1973). Giving tight bounds on the number of k-sets is still open, with substantial gaps between the current best upper and lower bounds in all dimensions larger than or equal to 2. We propose to focus on the topological aspects of the depth function, in particular the occurrence of critical cells of different types; see Definition 1. In the top dimension, we have a chamber containing the north-pole (a minimum at depth 0), a chamber containing the south-pole (a maximum at depth n), and otherwise only non-critical chambers connecting the minimum to the maximum. There is nothing much topological to learn from such a bi-polar depth function, but its restrictions to common intersections of great-spheres display a richer topology, which can be studied with methods from discrete Morse theory (Forman 1998) and persistent homology (Edelsbrunner and Harer 2010). The core result in this paper is a system of Dehn–Sommerville type relations for level sets of the depth function. This is different but related to the more direct generalization of the Dehn–Sommerville relations to levels in arrangements proved by Linhart et al. (2000). We refer to Grünbaum (1967, Sect. 9.2) for an introduction to the Dehn–Sommerville relations for convex polytopes. Similar to their classic relatives and the generalization in Linhart et al. (2000), our relations are based on double-counting, but instead counting cells, we take sums of topological indicators. To state the relations, let A be an arrangement of n great-spheres in Sd, and write Ckp(A) for the number of p-cells at depth k in A. For each p-cell, consider the alternating sum of its faces at the same depth, and write Ekp(A) for the sum of such alternating sums over all p-cells at depth k. If A is simple (see Sect. 2.1 for a definition), then we have a system of linear relations for 0≤p≤d and 0≤k≤n-d+p:1 ∑i=0p(-1)id-id-pEki(A)=Ckp(A)=∑i=0pd-id-pEk+i-pi(A),

which we refer to as Dehn–Sommerville–Euler relations. The system has applications to cyclic polytopes—which are convex hulls of finitely many points on the moment curve—and the broader class of neighborly polytopes—which are characterized by the property that every (q-1)-simplex spanned by q≤d/2 vertices is a face of the polytope. A celebrated result in the field is the Upper Bound Theorem proved by McMullen (1970), which states that every cyclic polytope has at least as many faces of any dimension as the convex hull of any other set of n points in Rd. All cyclic polytopes with n vertices in Rd have isomorphic face complexes with a structure that is simple enough to allow for counting the faces, and expressions for these numbers can be found in textbooks, such as Ziegler (1995). In contrast, neighborly polytopes with n vertices in Rd can have non-isomorphic face complexes, but they still have the same number of faces in every dimension. Within our framework, the structural simplicity is expressed by having bi-polar restrictions of the depth function to the intersection of any q≤d/2 great-spheres. We call an arrangement in Sd that has this property a neighborly arrangement. Writing p=d-q and counting only the cells of the subarrangement, B, in the intersection of the q great-spheres, straightforward topological arguments imply2 Ekp(B)=1fork=0,0for1≤k≤n+p-d-1,(-1)pfork=n+p-d.

Together with the Dehn–Sommerville–Euler relations in (1), this implies expressions in n, d, p, and k for the number of p-faces, for every 0≤p≤d, and thus generalizes the result for convex polytopes to levels in neighborly arrangements. Surprisingly, the neighborly property not only determines the number of faces of the convex hull but in fact of every level of the corresponding dual arrangement. The special case of cyclic polytopes, in which the hyperplanes are dual to points on the moment curve, has been solved in Andrzejak and Welzl (2003).

Outline Sect. 2 presents the background needed for the results in this paper. Section 3 studies the face and coface structure of a cell in an arrangement. Section 4 uses the technical lemmas in Sect. 3 to prove the system of relations (1), which it compares with the more classic extension of the Dehn–Sommerville relations in Linhart et al. (2000). Section 5 reproduces known bounds on the size of higher-order Voronoi tessellations in two and three dimesions from our system of relations. Section 6 uses (1) to generalize results for neighborly polytopes to neighborly arrangements. Section 7 concludes the paper.

Background

In this section, we introduce the main geometric and topological concepts studied in this paper: arrangements, depth functions, and sublevel sets.

Arrangements

As mentioned in Sect. 1, we study the properties of a finite point set in the dual setting, where each point is represented by a non-vertical hyperplane. To further finesse the inconvenience of unbounded cells, we map every point in Rd to a (d-1)-dimensional great-sphere and consider the arrangement formed by these great-spheres in Sd. Besides having only bounded cells, the great-sphere arrangement is centrally symmetric and thus has two antipodal cells for each bounded cell and each pair of diametrically opposite unbounded cells in the hyperplane arrangement. A possible such transformation maps a point a=(a1,a2,…,ad)∈Rd to the hyperplane defined by the equation xd+ad=a1x1+a2x2+⋯+ad-1xd-1 and further to the great-sphere in Sd obtained by intersecting the unit-sphere in Rd+1 with the (d-dimensional) hyperplane defined by xd+adxd+1=a1x1+a2x2+⋯+ad-1xd-1; see Fig. 1.Fig. 1 An arrangement of four lines in R2 on the left and the corresponding arrangement of four great-circles in S2 on the right

Two points in Sd are distinguished: the north-pole at the very top and the south-pole at the very bottom of the sphere. By construction, none of the great-spheres passes through the two poles. Letting σ be a great-sphere in Sd, we write σ- for the closed lower hemisphere bounded by σ, which contains the south-pole, and we write σ+ for the closed upper hemisphere, which contains the north-pole. Letting A be the collection of great-spheres, each cell in the arrangement corresponds to a tri-partition, A=A-⊔A0⊔A+, such that the cell is the common intersection of the lower hemispheres σ-, with σ∈A-, the great-spheres σ, with σ∈A0, and the upper hemispheres σ+, with σ∈A+. We write A for the arrangement defined by A, we refer to a cell of dimension p as a p-cell, and for p=0, 1, 2, d-1, d, we call it a vertex, edge, polygon, facet, chamber, respectively. The faces of a cell are the cells contained in it, which includes the cell itself.

The intersection of great-spheres is again a great-sphere, albeit of a smaller dimension. To avoid any confusion, we will explicitly mention the dimension if it is less than d-1. We call the arrangement simple if all great-spheres avoid the two poles and the common intersection of any d-p great-spheres is a p-dimensional great-sphere in Sd. This implies that any d great-spheres intersect in a pair of antipodal points, and any d+1 or more great-spheres have an empty common intersection. For each 0≤p≤d, we write Cp=Cp(A) for the number of p-cells in the arrangement, and Cp(n,d) for the maximum over all arrangements of n great-spheres in Sd. Importantly, the number of cells is maximized if the arrangement is simple, and in this case it depends on the number of great-spheres but not on the great-spheres themselves.

Proposition 1

(Number of cells) Any simple arrangement of n≥d great-spheres in Sd has Cp(n,d)=2dpnd+d-2p-2nd-2+⋯+d-2ip-2ind-2i p-cells, in which i=p/2.

The formula for the number of p-cells is not new and can be derived from similar formulas for arrangements in d-dimensional real projective space (Grünbaum 1967, Sect. 18.1) or in d-dimensional Euclidean space (Edelsbrunner 1987, Sect. 1.2).

Depth function

Given a set A of n great-spheres in Sd, none passing through the two poles, we define the depth of a point x∈Sd as the number of great-spheres σ∈A with x∈σ-\σ. In words, the depth of the point is the number of great-spheres that cross the shortest arc connecting x to the north-pole. If x and y are two interior points of the same cell, then they have the same depth. Recalling that A is the arrangement defined by A, we introduce the depth function, θ:A→[0,n], which we define by mapping each cell to the depth of its interior points. Depending on the situation, we think of θ as a discrete function on the arrangement or a piecewise constant function on Sd, namely constant in the interior of every cell in A.

Let c be a p-cell in A, with corresponding tri-partition A-⊔A0⊔A+. The depth of every interior point x∈c is θ(x)=θ(c)=#A-, and if the arrangement is simple, then p=d-#A0. Let b⊆c be a face of dimension i≤p, with corresponding tri-partition B-⊔B0⊔B+. We have B-⊆A-, A0⊆B0, B+⊆A+, and if the arrangement is simple, we also have i=d-#B0. Given the depth of c, this implies the following bounds on the depth of b:

Lemma 1

(Depth of face) Let A be a simple arrangement of great-spheres in Sd. For every i-face, b, of a p-cell, c, we have max{0,θ(c)+i-p}≤θ(b)≤θ(c), and both bounds on the depth of b are tight.

Proof

Since the arrangement is simple, we have #B-≥#A--[#B0-#A0]=#A-+i-p, which implies the first inequality. The second inequality follows from #B-≤#A-, which holds for general and not necessarily simple arrangements.

To prove the second inequality is tight, we show the existence of a p-cell that shares b with c and has the same depth as b. To this end, consider the tri-partition (B+∪X)⊔(B0\X)⊔B-, in which X⊆B0 has cardinality p-i. The cell defined by this tri-partition is non-empty because it contains b as a face. Furthermore, this cell has dimension p and the same depth as b. The proof that the first inequality is tight is symmetric and omitted. □

To relate this concept to the prior literature, we mention that Edelsbrunner (1987, Chapter 3) introduces the k-th level of an arrangement of n non-vertical hyperplanes in d dimensions as the points x∈Rd below fewer than k and above fewer than n-k of the hyperplanes. In other words, the k-th level consists of all facets at depth k-1 and all their faces. Assuming the arrangement is simple, Lemma 1 implies that a p-cell belongs to the k-th level iff its depth is between k-d+p and k-1.

Sublevel sets

Assume that A has at least one vertex, which in the simple case is implied by n≥d. For 0≤k≤n, we write Ak=θ-1[0,k] for the sublevel set of θ at k. It consists of all cells in A whose depth is k or less. Recall that θ is monotonic, by which we mean that the depth of every cell is at least as large as the depth of any of its faces. It follows that Ak is a complex, with well defined Euler characteristic:3 χ(Ak)=∑c∈Ak(-1)dimc.

The right-hand side of (3) explains how the Euler characteristic changes from Ak-1 to Ak, namely by adding the alternating sum of all cells at depth k. By Lemma 1, every cell at depth k is a face of a chamber at depth k. We can therefore construct Ak from Ak-1 by adding all chambers at depth k together with their faces at the same depth. This motivates the following two definitions.

Definition 1

(Relative Euler and depth characteristic) For a cell c∈A, let F=F(c) be the complex of faces, which includes c, and let F0⊆F be a subcomplex. The relative Euler characteristic of the pair of complexes is χ(F,F0)=∑b∈F\F0(-1)dimb.

If F0 is the set of faces b⊆c with θ(b)<θ(c), denoted U=U(c), we call ε(c)=χ(F,U) the depth characteristic of c, and we call c critical for θ if ε(c)≠0.

For example, if all faces have the same depth as c, then the depth characteristic of c is ε(c)=χ(F,∅)=1, and if all proper faces have depth strictly less than c, then the depth characteristic of c is ε(c)=χ(F,F\{c})=(-1)dimc. In both cases, c is critical.

Lemma 2

(Relative and absolute Euler characteristic) Let F=F(c) be the face complex of a cell, c, in an arrangement, and let F0⊆F be a subcomplex. Then the relative Euler characteristic of the pair is χ(F,F0)=1-χ(F0).

Proof

By definition, χ(F,F0)+χ(F0) is the sum of (-1)dimb over all cells b∈F\F0 as well as all b∈F0, and therefore over all b∈F. Hence, this sum is χ(F), which is equal to 1 because c is closed and convex. The claimed equation follows. □

We write Ckp=Ckp(A) for the number of p-cells at depth k, and Ekp=Ekp(A)=∑cε(c) for the sum of depth characteristics over all p-cells at depth k. To see the motivation behind taking sums of depth characteristics, consider the subcomplex of cells at depth at most k in a p-dimensional subarrangement of the d-dimensional arrangement. It is pure p-dimensional, by which we mean that every cell in this subcomplex is a face of a p-cell. Furthermore, the Euler characteristic of this pure complex is the sum of depth characteristics of its p-cells. In other words, we can construct the subarrangement by adding its p-cells in the order of non-decreasing depth. Whenever we add a p-cell, c, we also add the yet missing faces, and we know that ε(c) is the increment to the Euler characteristic of the subcomplex. Hence, Ekp is the increment to the total Euler characteristic of the subcomplexes in the p-dimensional subarrangements when we add the p-cells at depth k together with their yet missing faces.

Local configurations

Most arguments in the subsequent technical sections accumulate local quantities, each counting faces or cofaces of a cell. In a simple arrangement, the coface structure depends only on the dimension, so we study it first.

Coface structure

In the generic case, the local neighborhood of a vertex in an arrangement in Sd looks like that of the origin in the arrangement of the d coordinate planes in Rd. Each of these (d-1)-planes bounds an open half-space in which the corresponding coordinate is strictly negative. Accordingly, we define the depth of a point x∈Rd as the number of negative coordinates, and the depth of a cell in the arrangement as the depth of its interior points. To study this arrangement, consider [-1,1]d⊆Rd and let Sp(d) be the number of q-sides of the d-cube, in which we write q=d-p. The dual correspondence provides an incidence reversing bijection between the p-cells of the arrangement and the q-sides of the cube.Fig. 2 The neighborhood of the origin in R3 and the dual cube centered at the origin. The labels of the sides are the depths of the corresponding cells in the arrangement of coordinate planes

We label each side with the depth of the corresponding cell in the arrangement, and write Skp(d) for the number of q-sides labeled k. As illustrated in Fig. 2, this amounts to labeling Skd(d)=dk vertices with k, for 0≤k≤d, and labeling each side with the minimum label of its vertices. Note that the label of a q-side cannot exceed d-q=p.

Lemma 3

(Coface structure of vertex) Consider the arrangement defined by the d coordinate planes in Rd. (i) For 0≤k≤p≤d, the number of p-cells at depth k is Skp(d)=d-kd-pdk.

(ii) There is one cell at depth d, namely the negative orthant, and for 0≤k<d, the alternating sum of cells at depth k vanishes; that is: ∑p=kd(-1)pSkp(d)=0.

Proof

The p-cells counted in (i) correspond to the q-sides with label k, in which p+q=d. To count these q-sides, we recall that the d-cube has dk vertices at depth k. For each such vertex, u, consider the largest side for which u is the vertex with minimum label. This largest side is a cube of dimension d-k, which contains d-kq q-sides incident to u. We thus get4 Skp(d)=d-kqdk=d-kd-pdk

q-sides with label k, which proves (i).

To see (ii), consider a (d-k)-cube with label k. The alternating sum of sides with the same label is ∑q=0d-k(-1)qd-kq, which vanishes for d-k>0, and equals 1 for d-k=0. Likewise, the sum of alternating sums over all (d-k)-sides with label k vanishes for d-k>0 and equals 1 for k=d. This implies (ii) by duality. □

It is easy to generalize Lemma 3 from a vertex to a cell of dimension i≥0. To see this geometrically, we slice the i-cell and its cofaces with a (d-i)-plane orthogonal to the i-cell. In this slice, the i-cell appears as a vertex, and each coface of dimension p appears as a (p-i)-cell.

Corollary 1

(Coface structure of cell) Consider the arrangement defined by the d coordinate planes in Rd, and let c be an i-cell at depth 0≤ℓ≤i. (i) For 0≤k-ℓ≤p-i≤d-i, the number of p-cells at depth k that contain c is Sk-ℓp-i(d-i)=d-i-k+ℓd-pd-ik-ℓ.

(ii) There is one cell at depth d, and for ℓ≤k<d, the alternating sum of cells at depth k that contain c vanishes; that is: ∑p=kd(-1)pSk-ℓp-i(d-i)=0.

Face structure

The face structure of a cell in a simple arrangement is not quite as predictable as its coface structure. Nevertheless, we can say something about it. As before, we write F=F(c) for the face complex of a cell, c, and we let F0⊆F be a subcomplex. Furthermore, we write5 X(F,F0)=∑b∈F\F0(-1)dimbχ(F(b),F0∩F(b))

for the alternating sum of relative Euler characteristics.

Lemma 4

(Face structure of cell) Let c be a cell in a simple arrangement of great-spheres in Sd, and let F0⊆F(c) be a subcomplex of the face complex of the cell. Then X(F,F0)=1 if F0≠F and X(F,F0)=0 if F0=F.

Proof

If F0=F, then X(F,F0) is a sum without terms, which is 0. We can therefore assume F0≠F, which implies c∈F\F0. Fix a cell a∈F\F0 with dimension i=dima less than or equal to p=dimc. It contributes (-1)i+j for every j-cell b∈F\F0 that contains a as a face. The contribution of a to X(F,F0) is therefore (-1)i∑j=1p(-1)jp-ij-i, which vanishes for all i<p and is equal to 1 for i=p. Hence, the only non-zero contribution to X(F,F0) is for a=c, which implies the claim. □

There is a symmetric form of the lemma, which we get by introducing the codepth function, ϑ:A→[0,n] defined by ϑ(x)=n-q-θ(x), where q is the number of great-spheres that pass through x. Observe that ϑ(x) is the number of great-spheres that cross the shortest arc connecting x to the south-pole. We write Bℓp(A) for the number of p-cells with codepth ℓ. If the arrangement is simple, then6 Bℓp(A)=Ckp(A),withk+ℓ+(d-p)=n.

Indeed, there are d-p great-spheres that contain a p-cell, c, and if k great-spheres pass above c, then ℓ=n-(k+d-p) great-spheres pass below c. Recall that ε(c)=χ(F,U) is the depth characteristic, in which F=F(c) is the face complex, and U⊆F is the subcomplex of faces at depth strictly less than θ(c). Symmetrically, we call δ(c)=χ(F,L) the codepth characteristic of c, in which F=F(c) as before, and L⊆F is the subcomplex of faces at codepth strictly less than ϑ(c). In a simple arrangement, the two characteristics agree on even-dimensional cells, and they are the negative of each other for odd-dimensional cells.

Lemma 5

(Depth and codepth characteristics) For a p-cell in a simple arrangement of great-spheres, we have δ(c)=(-1)pε(c).

Proof

The boundary of c is a (p-1)-sphere, which is decomposed by the complex of proper faces of c. We write L for the proper faces with codepth strictly less than ϑ(c), and U for the proper faces with depth strictly less than θ(c). L and U exhaust the proper faces of c. More precisely, L and U partition the (p-1)-faces, and each of the two subcomplexes is the closure of its set of (p-1)-faces. Hence, L∩U consists of all (p-2)-faces shared by a (p-1)-face in L and another (p-1)-face in U, together with all faces of these (p-2)-faces. Since the arrangement is simple, the cells in L∩U decompose a (p-2)-manifold.Case 1: p is odd. Then L∩U decomposes an odd-dimensional manifold. By Poincaré duality, χ(L∩U)=0. The Euler characteristic of the boundary of c is 2, which implies χ(L)+χ(U)-χ(L∩U)=χ(L)+χ(U)=2. By Lemma 2, ε(c)=1-χ(U) and therefore δ(c)=1-χ(L)=1-[2-χ(U)]=-ε(c), as claimed.

Case 2: p is even. The boundary of c is an odd-dimensional sphere, so its Euler characteristic vanishes. By Alexander duality, χ(L)=χ(U), and by Lemma 2, ε(c)=1-χ(U) and δ(c)=1-χ(L), which implies δ(c)=ε(c), as claimed.□

Relations

In this section, we prove linear relations for the cells at given depths. The relations are similar to the classic Dehn–Sommerville relations for convex polytopes, and we prove them the same way by straightforward double counting; see Grünbaum (1967, Sect. 9.2). We begin with the easy bi-polar case.

Bi-polar depth functions

We recall that the depth function on an arrangement of great-spheres is bi-polar if there is a chamber above all great-spheres. By construction, the arrangement and its depth function are antipodal, which implies that there is also a chamber below all great-spheres. With the great-spheres given in Sd, the depth function on Sd is necessarily bi-polar, but its restrictions to subarrangements inside the common intersection of one or more great-spheres are not necessarily bi-polar.

Theorem 1

(Bi-polar depth functions) Let A be a simple arrangement of n≥d great-spheres in Sd, let B be the p-dimensional subarrangement inside the intersection of d-p of the great-spheres, and assume that the restriction of the depth function to B is bi-polar. Then7 Ekp(B)=1fork=0,0for1≤k≤n-d+p-1,(-1)pfork=n-d+p.

Proof

Let cN be the (p-dimensional) chamber at depth 0 in B, and let cS be the antipodal chamber at depth n-d+p. We write Sp for the intersection of the d-p great-spheres, fix a point N∈Sp inside the interior of cN, and let S∈Sp in the interior of cS be the antipodal point. We partition Sp\{N,S} into open fibers, each half a great-circle connecting N to S. Along each fiber, the depth is non-decreasing. Consider the set of fibers that intersect a chamber c≠cN,cS. They partition the boundary of c into the upper boundary, along which the fibers enter the chamber, the lower boundary, along which the fibers exit the chamber, and the silhouette, along which the fibers touch but do not enter the chamber. Since c is p-dimensional and spherically convex (the common intersection of closed hemispheres) this implies that the silhouette is a (p-2)-sphere, and the upper and lower boundaries are open (p-1)-balls. The depth characteristic of c is (-1)p-1—for the open lower boundary—plus (-1)p—for the chamber itself. It follows that the depth characteristic of c vanishes, and so does the depth characteristic of every other chamber, except for cN and cS. Because cN has the same depth as its entire boundary, we have ε(cN)=1, and because cS has larger depth than its entire boundary, we have ε(cS)=(-1)p. This implies (7). □

Alternating sums of depth characteristics

In the general case, the restrictions of the depth function to subarrangements are not necessarily bi-polar. The depth characteristics may therefore violate (7), but they satisfy a system of linear relations, as we prove next.

Theorem 2

(Dehn–Sommerville–Euler for levels) Let A be a simple arrangement of n≥d great-spheres in Sd. Then for every dimension 0≤p≤d, we have8 ∑i=0p(-1)id-ip-iEki(A)=Ckp(A)=∑i=0pd-ip-iEk+i-pi(A)for0≤k≤n-d+p.

Proof

Let c be a p-cell at depth k, let F=F(c) be the face complex of c, and let U⊆F be the subcomplex of faces at depth strictly less than k. Note that U does not contain c, so U≠F, and Lemma 4 implies X(F,U)=1. Taking the sum over all p-cells at depth k thus gives the number of such p-cells, which is Ckp(A). By Corollary 1 (i), a single i-cell contributes to the alternating sums of S0p-i(d-i)=d-ip-i p-cells, which implies that the first sum in (8) is the total alternating sum of depth characteristics over all cells at depth k and dimension at most p.

The second relation in (8) is the upside-down version of the first relation. Indeed, we can substitute codepth for depth and get the following relation using the notation of Sect. 3.2:9 Bℓp(A)=∑i=0p(-1)id-ip-iDℓi(A).

To translate this back in term of depth, we set ℓ=n-(k+d-p) so that a p-cell at codepth ℓ has depth n-(ℓ+d-p)=k. Hence, Bℓp(A)=Ckp(A). To write the Ds in terms of the Es, we multiply with (-1)i because of Lemma 5, and we change the index from ℓ=n-(k+d-p) to k+i-p=n-(ℓ+d-i) because of (6). This gives the right relation in (8). □

As an example consider the case d=2. We get equations (10)–(12) by setting p=0,1,2 in (8):10 Ek0=Ck0=Ek0,

11 2Ek0-Ek1=Ck1=2Ek-10+Ek1,

12 Ek0-Ek1+Ek2=Ck2=Ek-20+Ek-11+Ek2,

Equation (10) just says that the depth characteristic of every vertex is 1. (11) implies Ek1=Ek0-Ek-10, and (12) implies Ek1+Ek-11=Ek0-Ek-20, which follows from the relation implied by (11). Note that adding the depth characteristics of the edges gives a telescoping series, which implies E01+E11+…+Ek1=Ek0.

Alternating sums of cells

For comparison, we state the more traditional version of the Dehn–Sommerville relations, which apply to cell complexes; see Mulmuley (1993) and Linhart et al. (2000, Theorem 1). It counts the p-cells at depth k, which together with all their faces form a cell complex. For each dimension 0≤i≤p, this includes all i-cells at depths k+i-p to k.

Proposition 2

(Dehn–Sommerville for levels) Let A be a simple arrangement of n≥d great-spheres in Sd. For every dimension 0≤p≤d, we have13 Ckp(A)=∑i=0p(-1)id-id-p∑j=0p-ip-ip-i-jCk+i-p+ji(A)for0≤k≤n-d+p.

We get a non-trivial relation in (13) for p=1, which asserts Ck1=dCk-10+dCk0-Ck1. Indeed, twice the number of edges is the sum of vertex degrees. For p=2, we get14 Ck2=d2Ck0-(d-1)Ck1+Ck2+(d-1)dCk-10-(d-1)Ck-11+d2Ck-20,

in which the polygons cancel and the rest is equivalent to the relation for p=1. More generally, the term on left-hand side of (13) cancels whenever p is even.

Application to higher-order Voronoi tessellations

In this section, we give evidence for the unifying power of the system of Dehn–Sommerville–Euler relations by rederiving cell-counting formulas for higher-order Voronoi tessellations proved in Biswas et al. (2021) and Lee (1982). The difference forms of the relations are particularly convenient, which we present in dimensions 3 and 4.

Two dimensions

Before discussing the 2-dimensional order-k Voronoi tessellations, we introduce the 3-dimensional difference relations implied by Theorems 1 and 2.

Corollary 2

(Difference relations in S3) Let A be a simple arrangement of n≥3 great-spheres in S3. Then15 Ek1(A)=32[Ek0(A)-Ek-10(A)],for0≤k≤n,

16 Ek2(A)=13[Ek1(A)-Ek-11(A)]+2,for0≤k≤n,

17 Ek3(A)=1fork=0,0for1≤k≤n-1,-1fork=n.

Proof

We get (15) by setting d=3 and p=1 in (8) and (17) by setting d=p=3 in (7). To get (16), we begin by setting d=p=3 in (8), which gives18 Ek2-Ek-12=[Ek-30-Ek0]+[Ek-21+Ek1]+2Ek3=13[Ek1-2Ek-11+Ek-21]+2Ek3,

in which we use Ek-30-Ek0=-23[Ek1+Ek-11+Ek-21] implied by (15). Moving Ek-12 to the right-hand side and substituting it recursively implies (16) because ∑ℓ=0kEℓ3=1 by (17). □

If every 2-dimensional subarrangement is bipolar, then each arrangement of n-1 great-circles inside a great-sphere has polygons of predictable depth characteristics, namely a minimum (with depth characteristic 1) at depth 0, a maximum (with depth characteristic 1) at depth n-1, and otherwise only non-critical polygons connecting the minimum to the maximum. Hence,19 Ek2(A)=nfork=0,n-1,0for1≤k≤n-2,

20 Ek1(A)=3n-6(k+1)for0≤k≤n-2,

21 Ek0(A)=2n(k+1)-4k+22for0≤k≤n-3,

in which we get (20) from (19) and (16), and we get (21) from (20) and (15). For values of k outside the given limits, the sums of Euler characteristics are zero.

As defined in Shamos and Hoey (1975), the order-k Voronoi tessellation of n points in R2 is a decomposition of the plane into closed convex regions such that any two points in a region share the same k nearest points in the given set; but see also Toth (1976). It can be obtained by mapping each of the n points, u=(u1,u2), to the plane x3=u1x1+u2x2+12(u12+u22), forming the arrangement of the n planes, and projecting the chambers at depth k to the regions of the tessellation. The boundaries of the regions are obtained by projecting the edges at depth k-1 and the vertices at depths k-2 and k-1. Lee counted the regions, edges, and vertices in these tessellations (Lee 1982), and found that the numbers depend on n and k but barely on how the points are placed in the plane. Indeed, if we modify the setting slightly by turning the planes into great-spheres—as explained in Sect. 2—then a general position assumption suffices for these numbers to depend solely on n and k. Using Theorem 2 and the expressions for Eℓp in the case of bipolar 2-dimensional subarrangements given in (21), (20), (19), (17), we get22 Ck-20+Ck-10=Ek-20+Ek-10=2(n-k)(2k-1)-2k,

23 Ck-11=3Ek-20+Ek1=3(n-k)(2k-1)-3k,

24 Ck3=Ek-30+Ek-20+Ek-10+Ek0=(n-k)(2k-1)-k+2

for the number of vertices, edges, and regions. Modulo the difference between R2 and S2, these are the same expressions as in Lee (1982).

Three dimensions

Before discussing the 3-dimensional order-k Voronoi tessellations, we introduce the 4-dimensional difference relations implied by Theorems 1 and 2.

Corollary 3

(Difference relations in S4) Let A be a simple arrangement of n≥4 great-spheres in S4. Then25 Ek1(A)=2[Ek0(A)-Ek-10(A)],for0≤k≤n,

26 Ek2(A)=12[Ek1(A)-Ek-11(A)]+∑ℓ=0kEℓ3,for0≤k≤n,

27 Ek4(A)=1fork=0,n,0for1≤k≤n-1.

Proof

We get (25) by setting d=4 and p=1 in (8), and we get (27) by setting d=p=4 in (7). To get (26), we begin by setting d=4 and p=3 in (8), which gives28 Ek2-Ek-12=2[Ek-30-Ek0]+32[Ek-21+Ek1]=12[Ek1-2Ek-11+Ek-21]+Ek3,

in which we use 2[Ek-30-Ek0]=-[Ek1+Ek-11+Ek-21] implied by (25). Moving Ek-12 to the right-hand side and substituting iteratively, we get (26). □

Note the absence of any relation for Ek3. However, if we assume that all 3-dimensional subarrangements are bipolar, there is additional information about the facets and therefore also about the polygons:29 Ek3(A)=nfork=0,0for1≤k≤n-2,-nfork=n-1,

30 Ek2(A)=12[Ek1(A)-Ek-11(A)]+n,for0≤k≤n-2,

in which we get (30) from (29) and (26).

By straightforward generalization from 2 to 3 dimensions, the order-k Voronoi tessellation of n points in R3 decomposes space into convex regions, each associated with the k nearest of the n points. In analogy to the 2-dimensional case, we map the points to 3-planes in R4—or to great-spheres in S4—so that the tessellation is the projection of a subset of the cells. Despite this similarity, the expressions for the number of cells of the 2-dimensional tessellations derived by Lee (1982) have been extended to 3 dimensions only recently. The main reason for such delay is that the number of cells do not only depend on n and k, but also on how the points are distributed in space. Indeed, compared to the 2-dimensional case, we have the same number of relations but one more variable. Specifically, we have relations (25), (30), (29), (27), and we count vertices, edges, polygons, and (3-dimensional) regions, which are obtained by projecting the Ck-10+Ck-20+Ck-30 vertices at depths k-1,k-2,k-3, the Ck-11+Ck-21 edges at depths k-1,k-2, the Ck-12 polygons at depth k-1, and the Ck4 chambers at depth k. Using Theorem 2 and the four mentioned relations for bipolar 3-dimensional subarrangements, we get31 Ek-30+Ek-20+Ek-10=Ek-32+Ek-22+Ek-12-n2[3k2-3k+2],

32 4Ek-20-Ek-21+4Ek-10-Ek-11=2Ek-22+4Ek-12+2Ek2-2n[2k2-2k+1],

33 6Ek-10-3Ek-11+Ek-12=Ek-22+Ek-12-3n[k2-k],

34 Ek0-Ek1+Ek2-Ek3+Ek4=Ek-22-n2[k2-k+2]

for the number of vertices, edges, polygons, and regions in the order-k Voronoi tessellation for 1≤k≤n-1, in which Ek2=∑m=0k∑ℓ=0mEℓ2. To see that these are the same expressions as in Biswas et al. (2021), we note that Ek2=Nk+1 and Ek2=Jk+1 in the notation of that paper.

Application to neighborly arrangements

Recall that an arrangement in Sd is neighborly if the great-spheres are dual to the vertices of a neighborly polytope. Equivalently, all subarrangements of dimension p≥d/2 have bi-polar depth functions. We generalize the face-counting formulas for neighborly polytopes to the levels in neighborly arrangements. In particular, we show that the number of p-cells at depth k is a function of n, d, p, and k alone. For the special case of cyclic polytopes, this was proved before by Andrezejak and Welzl (2003, Theorem 5.1), who also derived explicit formulas for the number of cells.

Equations in matrix form

We write d=2t-1 for odd d and d=2t for even d. Let A be a neighborly arrangement of n great-spheres in Sd, so all subarrangements of dimension t≤p≤d are bi-polar. By Theorem 1, the Ekp are simple functions in n, d, p, and k, for all t≤p≤d. In addition, we get t independent relations for every k from Theorem 2. Specifically, for every odd p between 0 and d, we get a relation by equating the left-hand side of (1) with the right-hand side of (1). This gives what we call a giant linear system with variables Ek0 to Ekt-1 for 0≤k≤n. To describe it, we introduce the t×t matrices Md. For odd d, it is a straightforward configuration of binomial coefficients, which is however interrupted by -2s replacing -2t-j2i-2=-1 in row i and column j whenever 2t-j=2i-2:35 M2t-1=2t-10-2t-202t-30-2t-40…±t02t-12-2t-222t-32-2t-40…±t2⋮⋮⋮⋮⋱⋮2t-12t-4-2t-22t-42t-32t-4-2…02t-12t-2-200…0.

These replacements will be important shortly. For even d, the matrix M2t has the same number of entries, with 2t-j+12i-1 in row i and column j replacing 2t-j2i-2 in M2t-1. The -2s and 0s are the same in both matrices. In d dimensions, the giant system is given by a t(n+1)×t(n+1) matrix, with n+1 copies of Md along the diagonal. All entries to the lower left of this diagonal of t×t blocks are zero, while there are sporadic non-zero entries to the upper right.

Lemma 6

(Invertible blocks imply invertible systems) For every d≥1, if Md is invertible, then the giant system of linear relations in d dimensions is invertible.

Proof

If Md is invertible, then we can use row and column operations to turn Md into an upper triangular matrix with non-zero entries along the diagonal. Applying the same operations to the giant matrix, we get a giant upper triangular matrix with non-zero entries along the entire diagonal. □

Everything modulo 2

We prove the invertibility of M2t-1 by proving that its determinant is odd. Equivalently, we write P2t-1 for the matrix M2t-1 in which every entry is replaced by its parity, and we show that the mod 2 determinant of P2t-1 is 1. Before doing so, we show that the invertibility of M2t-1 implies the invertibility of M2t. Let N2t be the matrix M2t after dividing each column by the largest power of 2 that divides all its entries, and write P2t for the matrix N2t in which every entry is replaced by its parity.

Lemma 7

(Odd imply even invertible blocks) P2t=P2t-1.

Proof

Recall that the entry in row i and column j is 2t-j2i-2 in M2t-1 and 2t-j+12i-1 in M2t, unless this entry is -2 or 0, in which case it is the same in the two matrices. Assuming the former case, the ratio of the two entries is 2t-j+12i-1/2t-j2i-2=(2t-j+1)/(2i-1). Since 2i-1 is odd, the largest power of 2 that divides 2t-j+12i-1 is the largest power of 2 that divides 2t-j2i-2 times the largest power of 2 that divides 2t-j+1. The latter is the same for all entries in a column. We thus divide column j in M2t by the largest power of 2 that divides 2t-j+1, which is 1 for all even j. The even columns of M2t are the ones that contain the -2s, so after dividing, the parities of corresponding terms in M2t and M2t-1 are the same. Equivalently, P2t=P2t-1. □

Henceforth, we focus on the odd case. We use a consequence of Kummer’s theorem (Kummer 1852) to get the parity version of M2t-1:

Lemma 8

(Odd binomial coefficients) For all 0≤k≤n, nk is odd iff the binary representations of n, k, and n-k satisfy n2=k2xor(n-k)2.

In words: the 1s in the binary representations of k and n-k are at disjoint positions. It follows that the positions of the 1s in the binary representation of k are a subset of the positions of the 1s in the binary representation of n, and similarly for n-k and n. A compelling visualization of Lemma 8 is the Pascal triangle in binary, whose 1s form the Sierpinski gasket as shown in Fig. 3.Fig. 3 The Pascal triangle in modulo 2: the blue bricks are odd entries, and the white bricks (not shown) are even entries (colour figure online)

To transform the Sierpinski gasket into a matrix that contains P2t-1, for every t≥1, we drop every other up-slope (whose label, given along the down-slope in Fig. 3, is odd), we draw the remaining up-slopes as rows, and we draw the horizontal lines in the gasket as columns. Finally, we convert the last 1 in each row to a 0. These are the binomial coefficients that change from -1 to -2 in M2t-1; see Fig. 4.Fig. 4 Each blue and pink square is a 1 in the matrix, and each white square is a 0 (only those originally equal to -2 are shown). The bold black frames mark the exponential blocks, the bold red frame marks the 11-th block, P21, and the pink boxes inside the red frame mark the tops and bottoms of the NE- and SW-incursions that arise in its reduction (colour figure online)

Reducing exponential blocks

Observe that P2t-1 is the submatrix consisting of the rows labeled 2i, for 0≤i≤t-1, and the columns labeled j, for t≤j≤2t-1; see Fig. 4. We call this the t-th block. For the time being, we focus on exponential blocks, for which t is a power of 2. Note the symmetry between the upper and lower halves of an exponential block: the bottom is a copy of the top, except that the last 1 in each row is turned into a 0. We use this property to reduce exponential blocks.

Reduction 1

(Exponential block) Let P2t-1 be an exponential block, with t=2n, and write s=2n-1. We reduce P2t-1 in three steps: For 0≤i≤s-1, add the row with label 2i+2s to the row with label 2i. Thereafter, we have a 1 in each row and each even column, and otherwise only 0s in the upper half of the exponential block.

Zero out the even columns in the lower half using the rows in the upper half. After consolidating the lower half by removing the even columns, which are all zero, we get an upper triangular matrix with 1s in the diagonal.

Reduce this upper triangular matrix to the s×s identity matrix. Adding the even columns back, we have a 1 in each row and each odd column, and otherwise only 0s in the lower half of the exponential block.

Assuming t=2n, the above reduction algorithm turns P2t-1 into a t×t permutation matrix, whose determinant is of course 1. This is the parity of the determinant of M2t-1, which is therefore non-zero. To extend this result to integers, t, that are not necessarily powers of 2, we need a few properties of an exponential block. Being a square matrix with t=2n rows and columns, it decomposes into four quarters of s=2n-1 rows and columns each. By combining the NE- and NW-quarters, we get the northern half of the exponential block, and we draw the line from its bottom-left to top-right corners, calling it the northern diagonal; see Fig. 4. Similarly, we merge the SE- and SW-quarters to get the southern half and draw the southern diagonal from the bottom-left to top-right corner. Note that the southern half of P2t-1 is a copy of everything to the right of the northern half, namely the exponential blocks of size 1,2,4,…,2n-1 plus the 0s below and to the right of them.

An NE-incursion is a submatrix whose bottom-left corner lies on the southern diagonal and whose top-right corner is the top-right corner of the exponential block. As an example consider the rows labeled 0 to 20 and columns labeled 21 to 16, which is an NE-incursion of P31 in Fig. 4. We decompose the NE-incursion into three rectangular matrices stacked on top of each other: the top, the middle, and the bottom, in which the top and bottom are twice as wide as they are high, and the middle fills the space in between. Importantly, the middle is zero, and the top and bottom combine to a square matrix whose structure is such that Reduction  1 can reduce it to the identity matrix.

Symmetrically, an SW-incursion is a submatrix whose top-right corner lies on the northern diagonal and whose bottom-left corner is the bottom-left corner of the exponential block. As an example consider the rows labeled 6 to 14 and columns labeled 15 to 14, which is an SW-incursion of P15 in Fig. 4. As before, we decompose the SW-incursion into three rectangular matrices, in which the top and bottom are twice as wide as they are high, and the middle consists of the remaining rows in between. The top and bottom combine again to a square matrix that can be reduced to the identity matrix by Reduction 1. However, the middle is not necessarily zero. On the other hand, all entries to the right of the top but still within the exponential block are zero.

Reducing general blocks

We thus have the necessary ingredients to reduce a not necessarily exponential block, P2t-1. Assuming t is not a power of 2, let u be the power of 2 such that u/2<t<u, and write s=u/2. The overlap of P2t-1 with P2u-1 is an NE-incursion of the latter.

Reduction 2

(NE-incursion) Let I be the overlap of P2t-1 and P2u-1. We reduce I and zero out portions of P2t-1 outside I: Combine the top and bottom of I and reduce it using Reduction 1.

Add back the middle, which we recall is 0.

Use the columns of the reduced I to zero out the rectangular regions of P2t-1 to the right of the top and bottom of I.

Step 1 may contaminate the regions to the right of the bottom of I with non-zero entries, but Step 3 cleans up the contamination at the end. We are thus left with an un-reduced submatrix of size (u-t)×(u-t), which we denote P2t-1′. It is a bottom-left submatrix but not necessarily an SW-incursion of P2s-1. Assuming s<2(u-t), there is a largest SW-incursion of P2s-1 contained in P2t-1′, which has the same number of rows as P2t-1′.

Reduction 3

(SW-incursion) Assume s<2(u-t) and let J be the largest SW-incursion of P2s-1 contained in P2t-1′. We reduce J as follows: Combine the top and bottom of J and reduce it using Reduction 1.

Add back the middle and zero it out using row operations.

We note that the regions of P2t-1′ to the right of the top and bottom of J are zero because J is an SW-incursion, and P2t-1′ is contained in P2s-1. Step 1 preserves this property, so Step 2 can zero out the middle without contaminating the remaining un-reduced matrix of size (s-u+t)×(s-u+t), which we denote P2t-1′′.

It is also possible that s≥2(u-t), in which case there is no non-empty SW-incursion of P2s-1 contained in P2t-1′. We thus substitute the SW-quarter of P2s-1 for P2s-1, or the SW-quarter of that SW-quarter, etc. This square matrix is a copy of the exponential block of the same size, so Reduction 3 still applies. Similarly, P2t-1′′ is a copy of the (s-u+t)-th block. Since s-u+t<t, we can reduce it by induction. The correctness of the reduction algorithms implies

Lemma 9

(Blocks are invertible) For every d≥1, Md is invertible.

Proof

For d=2t-1, Reductions 1–3 together with induction imply that P2t-1 can be reduced to the identity matrix. By Lemma 7 this is also the case for P2t. Since Pd is the parity version of Md, this implies that Md is invertible. □

Number of cells

The invertibility of the blocks implies the invertibility of the giant linear systems, which implies that the number of cells in the levels of neighborly arrangements are independent of the geometry of the great-spheres defining the arrangement.

Theorem 3

(Neighborly arrangements) Let A be a neighborly arrangement of n≥d great-spheres in Sd. Then the Ekp(A) and the Ckp(A) are functions of n, d, p, and k.

Proof

By Lemma 9, the matrix Md is invertible, which by Lemma 6 implies that the giant linear system created from Theorems 1 and 2 is invertible. Hence, the Ekp(A) of the d-dimensional arrangement are determined; that is: they are functions of n, d, p, and k, but not of the great-spheres defining the arrangement. By Theorem 2, the Ckp(A) are determined by the Ekp(A), so they are also functions of n, d, p, and k. □

As an example, consider a neighborly arrangement of n great-spheres in S4. All subarrangements of dimension 2, 3, and 4 have bi-polar depth functions, so we get the Ekp for p=2,3,4 from Theorem 1, and we use Theorem 2 to get them for p=0,1:36 Ek0=12(k+1)n(n-k-3)for0≤k≤n-4,

37 Ek1=n(n-2k-3)for0≤k≤n-3,

38 Ek2=n2,0,n2fork=0,1≤k≤n-3,k=n-2,

39 Ek3=n,0,-nfork=0,1≤k≤n-2,k=n-1,

40 Ek4=1,0,1fork=0,1≤k≤n-1,k=n.

Using the relations Ck0=Ek0, Ck1=4Ek0-Ek1, etc., from Theorem 2, we get the number of cells with given depth:41 Ck0=12(k+1)n(n-k-3)for0≤k≤n-4,

42 Ck1=n[n(2k+1)-2k2-6k-3]for0≤k≤n-3,

43 Ck2=n2,3nk(n-k-2),n2fork=0,1≤k≤n-3,k=n-2,

44 Ck3=n,n[(2k-1)n-2k2-2k+3],6n2,2n2,nfork=0,1≤k≤n-4,k=n-3,k=n-2,k=n-1,

45 Ck4=1,12n[n(k-1)-k2+3],n(n-3),n2,n,1fork=0,1≤k≤n-4,k=n-3,k=n-2,k=n-1,k=n.

Discussion

The main contribution of this paper is the introduction of the discrete depth function as a topological framework to approach questions in discrete geometry, and the establishment of the system of Dehn–Sommerville–Euler relations for levels of this function. We have illustrated the use of this system by rederiving known cell-counting formulas for order-k Voronoi tessellations in R2 and R3, and by extending the classic face-counting formulas for neighborly polytopes to the levels in neighborly arrangements. This work suggests further research to deepen our understanding of the framework:Establish effective relations expressing the connections between the restrictions of the depth function to subarrangements.

Relate the stability of the persistence diagrams of restrictions of the depth function to combinatorial questions in geometry.

While our framework sheds new light on well studied questions in discrete geometry, there is plenty of work that remains. The following questions are of particular interest:Give bounds on the topological quantities that arise in counting the regions of order-k Voronoi tessellations. As established in Biswas et al. (2021), the relevant quantity in R3 is the double sum of depth characteristics of the 2-dimensional cells (the polygons) in the corresponding arrangement of great-spheres in S4. How do these results extend beyond 3 dimensions?

Generalize the results on neighborly arrangements to counting the k-sets of general sets of n points in Rd. Specifically, use the framework of depth functions to improve the current best upper bounds on the maximum number of k-sets, which are O(n4/3) in R2 (Dey 1998), O(n5/2) in R3 (Sharir et al. 2001), and O(nd-εd) for a small constant ϵd>0 in Rd (Živaljević and Vrećica 1992).

Acknowledgements

The authors thank Uli Wagner and Emo Welzl for comments on an earlier version of this paper, and for pointing out related work in the prior literature.

Funding

Open access funding provided by Institute of Science and Technology (IST Austria). This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, Grant No. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
==== Refs
References

Andrzejak A Welzl E In between k-sets, j-facets, and i-faces: (i,j)-partitions Discrete Comput. Geom. 2003 29 105 131 10.1007/s00454-002-2778-4
Andrzejak, A., Welzl, E.: In between -sets, -facets, and -faces: -partitions. Discrete Comput. Geom. 29, 105–131 (2003)
Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., Saghafian, M.: Counting cells of order- Voronoi tessellations in with Morse theory. In: Proc. 37th Ann. Sympos. Comput. Geom., pp. 16:1–16:15 (2021)
Björner, A.: Topological methods. In: Graham, R., Grötschel, M., Lovász, L. (eds.) Handbook of Combinatorics, pp. 1819–1872. North-Holland, Amsterdam (1995)
Dey TK Improved bounds for planar k-sets and related problems Discrete Comput. Geom. 1998 19 373 382 10.1007/PL00009354
Dey, T.K.: Improved bounds for planar -sets and related problems. Discrete Comput. Geom. 19, 373–382 (1998)
Edelsbrunner H Algorithms in Combinatorial Geometry 1987 Heidelberg Springer
Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer, Heidelberg (1987)
Edelsbrunner H Harer JL Computational Topology. An Introduction 2010 Providence American Mathematical Society
Edelsbrunner, H., Harer, J.L.: Computational Topology. An Introduction. American Mathematical Society, Providence (2010)
Erdős P Lovász L Simmons A Straus EG Srivastava JN Dissection graphs of planar point sets A Survey of Combinatorial Theory 1973 Amsterdam North-Holland 139 149
Erdős, P., Lovász, L., Simmons, A., Straus, E.G.: Dissection graphs of planar point sets. In: Srivastava, J.N., et al. (eds.) A Survey of Combinatorial Theory, pp. 139–149. North-Holland, Amsterdam (1973)
Fejes Toth G Multiple packing and covering of the plane with circles Acta Math. Acad. Sci. Hung. 1976 27 135 140 10.1007/BF01896768
Fejes Toth, G.: Multiple packing and covering of the plane with circles. Acta Math. Acad. Sci. Hung. 27, 135–140 (1976)
Forman R Morse theory for cell complexes Adv. Math. 1998 134 90 145 10.1006/aima.1997.1650
Forman, R.: Morse theory for cell complexes. Adv. Math. 134, 90–145 (1998)
Grünbaum B Convex Polytopes 1967 London Wiley
Grünbaum, B.: Convex Polytopes. Wiley, London (1967)
Kummer EE Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen J. Reine Angew. Math. 1852 44 93 146
Kummer, E.E.: Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen. J. Reine Angew. Math. 44, 93–146 (1852)
Lee D-T On k-nearest neighbor Voronoi diagrams in the plane IEEE Trans. Comput. 1982 31 478 487
Lee, D.-T.: On -nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput. 31, 478–487 (1982)
Linhart J Yang Y Philipp M Arrangements of hemispheres and halfspaces Discrete Math. 2000 223 217 226 10.1016/S0012-365X(98)00360-4
Linhart, J., Yang, Y., Philipp, M.: Arrangements of hemispheres and halfspaces. Discrete Math. 223, 217–226 (2000)
Matoušek J Using the Borsuk–Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry 2008 2 Heidelberg Universitext, Springer
Matoušek, J.: Using the Borsuk–Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry, 2nd edn. Universitext, Springer, Heidelberg (2008)
McMullen P The maximum numbers of faces of a convex polytope Mathematika 1970 17 179 184 10.1112/S0025579300002850
McMullen, P.: The maximum numbers of faces of a convex polytope. Mathematika 17, 179–184 (1970)
Mulmuley, K.: Dehn–Sommerville relations, upper bound theorem, and levels in arrangements. In: Proc. 9th Ann. Sympos. Comput. Geom., pp. 240–146 (1993)
Shamos, M.I., Hoey, D.: Closest-point problems. In: Proc. 16th Ann. IEEE Symp. Found. Comput. Sci., pp. 151–162 (1975)
Sharir M Smorodinsky S Tardos G An improved bound for k-sets in three dimensions Discrete Comput. Geom. 2001 26 195 204 10.1007/s00454-001-0005-3
Sharir, M., Smorodinsky, S., Tardos, G.: An improved bound for -sets in three dimensions. Discrete Comput. Geom. 26, 195–204 (2001)
Ziegler GM Lectures on Polytopes 1995 New York Springer
Ziegler, G.M.: Lectures on Polytopes. Springer, New York (1995)
Živaljević, R.T.: Topological methods in discrete geometry. In: Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn., pp. 551–580. CRC Press, Boca Raton (2017)
Živaljević RT Vrećica ST The colored Tverberg’s problem and complexes of injective functions J. Combin. Theory Ser. A 1992 61 309 318 10.1016/0097-3165(92)90028-S
Živaljević, R.T., Vrećica, S.T.: The colored Tverberg’s problem and complexes of injective functions. J. Combin. Theory Ser. A 61, 309–318 (1992)
