# Many neighborly inscribed polytopes and Delaunay triangulations

Bernd Gonska* and Arnau Padrol†

Institut für Mathematik, Freie Universität Berlin, Germany

**Abstract.** We present a very simple explicit technique to generate a large family of point configurations with neighborly Delaunay triangulations. This proves that there are superexponentially many combinatorially distinct neighborly $d$-polytopes with $n$ vertices that admit realizations inscribed on the sphere. These are the first examples of inscribable neighborly polytopes that are not cyclic polytopes, and provide the current best lower bound for the number of combinatorial types of inscribable polytopes (and thus also of Delaunay triangulations). It coincides with the current best lower bound for the number of combinatorial types of polytopes.

**Résumé.** Nous présentons une technique explicite simple pour générer une large famille de configurations de points dont les triangulations de Delaunay sont neighborly. Cela prouve que le nombre de $d$-polytopes combinatoirement distincts avec $n$ sommets et admettant une réalization inscrite sur la sphère est surexponentiel. Ce sont les premiers exemples de polytopes inscriptibles neighborly qui ne sont pas des polytopes cycliques et ils donnent la meilleure borne inférieure actuelle pour le nombre de types combinatoires de polytopes inscriptibles (et donc aussi de triangulations de Delaunay). Cette borne coïncide avec la meilleure borne inférieure actuelle pour le nombre de types combinatoires de polytopes.

**Keywords:** neighborly polytope, inscribable polytope, Delaunay triangulation, number of combinatorial types

## 1 Introduction

A polytope is called *inscribable* if it is combinatorially equivalent to a polytope that has all its vertices on a sphere. The question of inscribability was raised for the first time by Steiner in 1832 [Ste32], who asked whether all 3-dimensional polytopes are inscribable. A negative answer was given by Steinitz in 1928 [Ste28]. For example, the Triakis tetrahedron, the polytope obtained by stacking a tetrahedron on top of each facet of a tetrahedron, is not inscribable.

A characterization of inscribable 3-polytopes was found by Hodgson, Rivin and Smith using hyperbolic geometry [HRS92, Riv96]. In higher dimension, however, the question of inscribability is still wide open. It is not even known which vectors appear as $f$-vectors of inscribable simplicial polytopes [Gon13].

<footnote>*Email: GonskaB@gmail.com.</footnote>

<footnote>†Email: arnau.padrol@fu-berlin.de. The research of Arnau Padrol is supported by the DFG Collaborative Research Center SFB/TR 109 “Discretization in Geometry and Dynamics”.</footnote>
Seidel [Sei87, Sei91] proved an upper bound theorem for the complexity of Delaunay triangulations in terms of neighborly polytopes. Indeed, Brown observed in 1979 [Bro79] that using a stereographic projection one can identify the combinatorial types of Delaunay triangulations in $\mathbb{R}^d$ with those of inscribable $(d+1)$-dimensional polytopes. Therefore, by McMullen's Upper Bound Theorem [McM70], the complexity of Delaunay triangulations is bounded by that of inscribable neighborly polytopes.

The existence of inscribable neighborly polytopes has been known since their discovery by Carathéodory [Car11], who found a realization of cyclic polytopes with all their vertices on a sphere. While many inscribed realizations of the cyclic polytope are known (c.f. [Sei91], [Gon13] and [GZ13]), no other example of inscribable neighborly polytope has been found.

Without the constraint of inscribability, Grünbaum [Grün03] found the first examples of non-cyclic neighborly polytopes. Even more, Shemer used a “sewing construction” to prove in 1982 that the number of combinatorial types of neighborly $d$-polytopes with $n$ vertices is of order $n^{\frac{n}{2}(1+o(1))}$ [She82]. This bound was recently improved in [Pad13a] (see also [Pad13b]), by proposing a new construction for neighborly polytopes, Gale sewing, that contains Shemer’s family. Even if this method cannot generate all neighborly polytopes, it can be used to show that there are at least $n^{\frac{d}{2}n(1+o(1))}$ different combinatorial types of labeled neighborly $d$-polytopes with $n$ vertices (as $n \to \infty$ with $d$ fixed). This is currently also the best lower bound for the number of combinatorial types of labeled $d$-polytopes with $n$ vertices.

Our main contribution in this paper is to show that all these neighborly polytopes are inscribable. To this end, we revisit the Gale sewing construction from [Pad13a] using a technique developed in [GZ13] to construct inscribable cyclic polytopes (see also [Gon13]). This provides a very simple construction (Theorem 5.3) for high dimensional inscribable neighborly polytopes (and hence also for neighborly Delaunay triangulations and dual-to-neighborly Voronoi diagrams).

As a consequence of this result, we see that the number of different labeled combinatorial types of inscribable neighborly $d$-polytopes with $n$ vertices is at least $n^{\frac{d}{2}n(1+o(1))}$ (as $n \to \infty$ with $d$ fixed). As a reference, the best upper bound for the number of different labeled combinatorial types of $d$-polytopes with $n$ vertices is of order $(n/d)^{d^2n(1+o(1))}$ when $\frac{n}{d} \to \infty$ (see [Alo86] and [GP86]). Hence, inscribable (neighborly) polytopes are more frequent than what one might have thought.

## 2 Preliminaries

Let $A = \{a_1, \dots, a_n\}$ be a full dimensional *point configuration* in $\mathbb{R}^d$ whose points are labeled by $\{1, \dots, n\}$. We will say that $A$ is in *general position* if no $d+1$ points lie in a common hyperplane and no $d+2$ points lie on a common sphere.

The convex hull of $A$ is a *polytope* $P := \text{conv}(A) \subset \mathbb{R}^d$ and the intersection of $P$ with a supporting hyperplane is a *face* of $P$. Faces of dimensions 0 and $d-1$ are called *vertices* and *facets*, respectively. If all facets of $P$ are simplices, then $P$ is *simplicial* and if $A$ is in general position, then $\text{conv}(A)$ is always simplicial. A face $F$ of a polytope $P$ is *visible* from a point $p$ if there is a point $x \in \text{relint}(F)$ such that the segment $[x, p]$ intersects $P$ only at $x$. In particular, if $p \in P$ then no face is visible from $p$.

A facet of a $d$-polytope $P$ is a *lower facet* if the last coordinate of its outer normal vector is negative. The *lower envelope* of $P$ is the polytopal complex consisting on the lower facets of $P$ and their faces. Analogue definitions hold for the *upper facets* and the *upper envelope*.

A face $F$ of $P$ is called an *equatorial face* if the projection $\pi$ that forgets the last coordinate maps $F$ onto a face of $\pi(P)$. If $A$ is in sufficient general position, then the dimensions of $F$ and $\pi(F)$ coincide for every equatorial face $F$. In particular, in this case there cannot be equatorial facets.
We will usually assume that $A$ is in convex position, i.e. it coincides with $\text{vert}(P)$, the set of vertices of $P$. In particular, each face $F$ of $P$ can be identified with the set of labels of the points $a_i \in F$. The face lattice of $P$ is then a poset of subsets of $\{1, \dots, n\}$. In this context, two vertex-labeled polytopes are combinatorially equivalent if their face lattices coincide. The equivalence classes under this relation are called labeled combinatorial types.

A polytope $P$ is $k$-neighborly if every subset of $k$ vertices of $P$ forms a face of $P$. No $d$-dimensional polytope other than the simplex can be $k$-neighborly for any $k > \lfloor \frac{d}{2} \rfloor$, which motivates the definition of neighborly polytopes as those that are $\lfloor \frac{d}{2} \rfloor$-neighborly.

McMullen's Upper Bound Theorem [McM70] states that the number of $i$-dimensional faces of a $d$-polytope $P$ with $n$ vertices is maximized by simplicial neighborly polytopes, for all $i$. A canonical example of neighborly polytope is the cyclic polytope, $C_n(d)$, obtained as the convex hull of $n$ points on any $d$-order curve in $\mathbb{R}^d$ [Stu87]. For example, the moment curve $\gamma: t \mapsto (t, t^2, \dots, t^d)$ is a $d$-order curve. In even dimensions, the trigonometric moment curve

$$ \tau: t \mapsto (\sin(t), \cos(t), \sin(2t), \cos(2t), \dots, \sin(\frac{d}{2}t), \cos(\frac{d}{2}t)) $$

is a $d$-order curve on the sphere, providing an inscribed realization of the cyclic polytope [Car11] (see also [Grü03, Exercise 4.8.23]).

A triangulation of a point configuration $A$ is a collection $\mathcal{T}$ of simplices with vertices in $A$, which we call cells, that cover the convex hull of $A$ and such that any pair of simplices of $\mathcal{T}$ intersects in a common face. A triangulation $\mathcal{T}$ of a point configuration $A \subset \mathbb{R}^d$ is neighborly if $\text{conv}(S)$ is a cell of $\mathcal{T}$ for each subset $S \subset A$ of size $|S| = \lfloor \frac{d+1}{2} \rfloor$.

The Delaunay triangulation $\mathcal{D}(A)$ of a point configuration $A \subset \mathbb{R}^d$ in general position is the triangulation that consists of all cells defined by the empty circumsphere condition: $S \in \mathcal{D}(A)$ if and only if there exists a $(d-1)$-sphere that passes through all the vertices of $S$ and all other points of $A$ lie outside this sphere. A cell that fulfills the empty circumsphere condition is a Delaunay cell. If $A$ is in general position, the empty circumsphere condition always defines a triangulation of $A$.

# 3 Liftings and triangulations

## 3.1 Lexicographic liftings

The main tool for our construction are lexicographic liftings, which are a way to derive $(d+1)$-dimensional point configurations from $d$-dimensional point configurations.

For an affine hyperplane $H = \{x \in \mathbb{R}^d | \langle x, v \rangle = c\}$ defined by a normal vector $v$ whose last coordinate is positive, a point $a \in \mathbb{R}^d$ is said to be above (resp. below) $H$ if $\langle a, v \rangle > c$ (resp. $\langle a, v \rangle < c$).

**Definition 3.1** Let $A = \{a_1, \dots, a_n\}$ be a configuration of $n \ge d+2$ labeled points in general position in $\mathbb{R}^d$.

A configuration $\hat{A} = \{\hat{a}_1, \dots, \hat{a}_n\}$ of $n$ labeled points in $\mathbb{R}^{d+1}$ is a Delaunay lexicographic lifting (or just a D-lifting) of $A$ (with respect to the order induced by the labeling) if for each $1 \le i \le n$ $\hat{a}_i = (a_i, h_i) \in \mathbb{R}^{d+1}$ for some collection of heights $h_i \in \mathbb{R}$ that fulfill:

(i) for each $i \ge d+2$, $|h_i| > 0$ is large enough so that if $h_i > 0$ (resp. $h_i < 0$) then $\hat{a}_i$ is above (resp. below) $H$ for every hyperplane $H$ spanned by $d+1$ points of $\{\hat{a}_1, \dots, \hat{a}_{i-1}\}$.
(ii) for each $i > d+2$, $\hat{a}_i$ is not contained in any of the circumspheres of any simplex spanned by $d+2$ points in $\{\hat{a}_1, \dots, \hat{a}_{i-1}\}$.

If $h_i \ge 0$ for every $1 \le i \le n$, the lexicographic lifting is called positive.

**Remark 3.2** If A is in general position, then any D-lifting $\hat{A}$ of A is also in general position. Furthermore, if A is in convex position, then so is $\hat{A}$.

<figure><img src="image_1.png" /><figcaption>**Fig. 1:** A point configuration $\{a_1, \dots, a_5\}$ (a) and one of its D-liftings $\{\hat{a}_1, \dots, \hat{a}_5\}$ (b). It fulfills conditions (i) (c) and (ii) (d). It is not a positive D-lifting since the height of $\hat{a}_4$ is negative.</figcaption></figure>

We omit the proof of this easy lemma.

**Lemma 3.3** For any point configuration in general position A, and for any D-lifting $\hat{A}$, every equatorial face of $\mathrm{conv}(\hat{A} \setminus \hat{a}_n)$ is visible from $\hat{a}_n$.

The following lemma is the link with the results presented in [Pad13a]. The oriented matroid of a D-lifting of A is completely determined by the oriented matroid of A and the signs of the heights. Indeed, it can be described using *lexicographic extensions*, for which we refer to [BLS+93, Section 7.2] (see also [Pad13a, Section 4.1]).

**Lemma 3.4** A D-lifting of A with heights $h_i$ realizes the dual oriented matroid of a lexicographic extension of the Gale dual of A $\setminus \{a_n\}$ with signature $[a_{n-1}^{-\mathrm{sign}(h_n) \mathrm{sign}(h_{n-1})}, \dots, a_{d+2}^{-\mathrm{sign}(h_n) \mathrm{sign}(h_{d+2})}]$.

## 3.2 Placing triangulations

The combinatorics of D-liftings are easily explained in terms of *lexicographic triangulations*. We refer to [DRS10, Section 4.3] for a detailed presentation, and we will only present here the parts that will be directly useful for us. Namely *placing triangulations* and their relation to positive lexicographic liftings. Here, we say that a face of a triangulation of A is *visible* if it is contained in a visible face of $\mathrm{conv}(A)$.

**Lemma 3.5** ([DRS10, Lemma 4.3.2]) Let $A = \{a_1, \dots, a_n\}$ be a point configuration and let $\mathcal{T}$ be a triangulation of the point configuration $A \setminus a_n$. Then there is a triangulation $\mathcal{T}'$ of A whose cells are

$$ \mathcal{T}' := \mathcal{T} \cup \{\mathrm{conv}(B \cup a_n) \mid B \text{ is a face of } \mathcal{T} \text{ visible from } a_n\}. $$

Moreover, $\mathcal{T}'$ is the only triangulation of A that contains all the cells of $\mathcal{T}$.
**Definition 3.6** The placing triangulation of A (with respect to the order induced by the labels) is the triangulation $T_n$ obtained iteratively as follows: $T_1$ is the trivial triangulation of $\{a_1\}$ and $T_i$ is the unique triangulation of $\{a_1, \dots, a_i\}$ that contains $T_{i-1}$.

**Lemma 3.7** ([DRS10, Lemma 4.3.4]) Let $\hat{A} \subset \mathbb{R}^{d+1}$ be a positive D-lifting of a configuration $A \subset \mathbb{R}^d$. Then the lower envelope of $\text{conv}(\hat{A})$ is combinatorially equivalent (as a simplicial complex) to the placing triangulation of $A$.

# 4 The construction

Our construction is based on the following theorems, which show how certain triangulations of certain D-liftings are always Delaunay (Proposition 4.1) and neighborly (Proposition 4.2).

The proof of Proposition 4.1 is inspired by [GZ13, Proposition 17], where a similar argument is used to prove that the cyclic polytope is inscribable (see also [Sei85] for a related result in the plane).

**Proposition 4.1** Let $A = \{a_1, \dots, a_n\}$ be a configuration of $n \ge d+2$ labeled points in general position in $\mathbb{R}^d$ and let $\hat{A}$ be a D-lifting of $A$. Then the Delaunay triangulation $\mathcal{T} := \mathcal{D}(\hat{A})$ coincides with the placing triangulation of $\hat{A}$.

**Proof:** The proof is by induction on $n$. If $n = d+2$ then both triangulations consist on the single simplex spanned by $\hat{A}$. Otherwise, let $\mathcal{T}'$ be the Delaunay triangulation of $\hat{A} \setminus \hat{a}_n$. By induction hypothesis, this is the placing triangulation of $\hat{A} \setminus \hat{a}_n$. Moroever, since the lifting fulfills condition (ii), every Delaunay cell of $\mathcal{T}'$ is still a Delaunay cell of $\mathcal{T}$. Now, by Lemma 3.5 the placing triangulation is the unique triangulation of $\hat{A}$ containing all the cells of $\mathcal{T}'$. $\square$

Proposition 4.2 can be deduced from the *Gale sewing* technique presented in [Pad13a, Theorem 4.2]. However, the original proof of the theorem exploits Gale duality and oriented matroid theory, while this primal proof is elementary. Moreover, this is the setting that will eventually allow us to prove inscribability in Theorem 5.3.

**Proposition 4.2** Let $A = \{a_1, \dots, a_n\}$ be a configuration of $n \ge d+2$ labeled points in convex general position in $\mathbb{R}^d$ and let $\hat{A}$ be a D-lifting of $A$. If $\text{conv}(A)$ is $k$-neighborly (as a polytope), then $\text{conv}(\hat{A})$ is $k$-neighborly (as a polytope) and the placing triangulation of $\hat{A}$ is $(k+1)$-neighborly (as a triangulation).

**Proof:** The proof of the first claim ($\text{conv}(\hat{A})$ is $k$-neighborly) is straightforward. Indeed, since $A$ is a projection of $\hat{A}$, every face of $\text{conv}(A)$ is a projection of an equatorial face of $\text{conv}(\hat{A})$. In particular, since every subset of $k$-points of $A$ is a face of $\text{conv}(A)$, the corresponding points must also form an equatorial face of $\text{conv}(\hat{A})$.

The second claim is proved by induction on $n$, and it is trivial when $n = d+2$. For $n > d+2$, let $\mathcal{T}$ be the placing triangulation of $\hat{A}$ and $\mathcal{T}'$ the corresponding placing triangulation of $\hat{A} \setminus \hat{a}_n$. Now fix a subset $S$ of $\hat{A}$ of size $k+1$. If $\hat{a}_n \notin S$, then $S$ forms a cell of $\mathcal{T}'$ by induction hypothesis, and hence of $\mathcal{T}$. Otherwise, if $\hat{a}_n \in S$, then $S' = S \setminus \hat{a}_n$ must be an equatorial face of $\text{conv}(\hat{A} \setminus \hat{a}_n)$, because $\text{conv}(A)$ is $k$-neighborly. By Lemma 3.3, $S'$ is visible from $\hat{a}_n$ and hence by the definition of the placing triangulation, $S$ must be a cell of $\mathcal{T}$. $\square$

The combination of these two propositions directly proves our main result.
**Theorem 4.3** Let $A = \{a_1, \dots, a_n\}$ be a configuration of $n \ge d+2$ labeled points in convex general position in $\mathbb{R}^d$ such that $\text{conv}(A)$ is $k$-neighborly, and let $\hat{A}$ be a $D$-lifting of $A$. Then $\text{conv}(\hat{A})$ is a $k$-neighborly polytope with vertex set $\hat{A}$ and its Delaunay triangulation is a $(k+1)$-neighborly triangulation.

# 5 Polytopes

We can easily adapt Proposition 4.2 to obtain a statement in terms of neighborly polytopes instead of neighborly triangulations. It suffices to do another suitable $D$-lifting.

For example, one can start with a $k$-neighborly $d$-polytope $P$ with $n$ vertices $A = \text{vert}(P) \subset \mathbb{R}^d$, then make a $D$-lifting of $A$ to obtain $\hat{A}$, and finally a positive $D$-lifting of $\hat{A}$ to obtain $\hat{\hat{A}}$. Then $\text{conv}(\hat{\hat{A}})$ is easily seen to be a $(d+2)$-dimensional $(k+1)$-neighborly polytope with $n$ points.

However, this polytope is not necessarily inscribed. To recover inscribed polytopes from Delaunay triangulations, we need the following classical result of Brown [Bro79] (cf. [GZ13, Proposition 13]).

**Lemma 5.1** Let $A = \{a_1, \dots, a_n\}$ be a configuration of $n$ points in $\mathbb{R}^d$ in general position, and let $\mathcal{D}(A)$ be its Delaunay triangulation. Then there is an inscribable simplicial $(d+1)$-polytope $P_A$ with $n+1$ vertices $\{\hat{a}_1, \dots, \hat{a}_n, \hat{a}_{n+1}\}$ whose faces are:

(i) $\hat{S}$ if $S$ is a cell of $\mathcal{D}(A)$ and

(ii) $\hat{a}_{n+1} \cup \hat{S}$ if $S$ is a face of $\text{conv}(A)$,

where $\hat{S} = \{\hat{a}_i | a_i \in S\}$.

An inscribed realization of $P_A$ can be found by inverting a stereographic projection.

We omit the proof of the next lemma, which only needs a combinatorial description of the face lattice of a positive lifting (cf. [DRS10, Lemma 4.3.4]).

**Lemma 5.2** If the Delaunay triangulation of $A$ coincides with its placing triangulation, then the polytope $P_A$ of Lemma 5.1 is combinatorially equivalent to the convex hull of a positive $D$-lifting of $A \cup \{a_{n+1}\}$ for any $a_{n+1} \in \mathbb{R}^d$.

As a direct consequence of the combination of Lemma 5.1 and Theorem 4.3, we obtain the following result. Observe how the strategy is to start with a $k$-neighborly $d$-polytope, lift it to a $(k+1)$-neighborly $(d+1)$-triangulation, and lift it again (with a positive lifting with the same order) to a $(k+1)$-neighborly $(d+2)$-polytope, which is inscribable.

**Theorem 5.3** Let $A = \{a_1, \dots, a_n\}$ be a $d$-dimensional configuration of $n \ge d+3$ points in convex general position such that $\text{conv}(A)$ is $k$-neighborly, let $\hat{A}$ be a $D$-lifting of $A$ and let $\hat{\hat{A}}$ be a positive $D$-lifting of $\hat{A}$.

Then $\text{conv}(\hat{\hat{A}})$ is an inscribable $(k+1)$-neighborly $(d+2)$-polytope. In particular, if $\text{conv}(A)$ is neighborly, so is $\text{conv}(\hat{\hat{A}})$.

**Proof:** By Proposition 4.1, the placing triangulation of $\hat{A} \setminus \hat{a}_n$ coincides with its Delaunay triangulation. Therefore, by Lemma 5.2, $\text{conv}(\hat{\hat{A}})$ is combinatorially equivalent to the inscribed polytope $P_{\hat{A} \setminus \hat{a}_n}$ of Lemma 5.1. This proves inscribability.
For $k$-neighborliness, observe that as a consequence of Lemma 3.7, every face of the placing triangulation of $\tilde{A}$ is also a face of $\mathrm{conv}(\tilde{A})$. Since the triangulation is $(k+1)$-neighborly by Proposition 4.2, then so is $\mathrm{conv}(\tilde{A})$. $\square$

In [Pad13a] it is proven that if $M$ is the Gale dual of a neighborly polytope, then by performing a lexicographic extension of $M$ by $p = [a_1^{\epsilon_1}, \dots, a_r^{\epsilon_r}]$ and a lexicographic extension of $M[p]$ by $q = [p^-, a_1^-, \dots, a_{r-1}^-]$ the resulting matroid $M[p][q]$ is the Gale dual of a neighborly polytope. This technique is called Gale sewing and the neighborly polytopes obtained by repeatedly Gale sewing from a polygon are called Gale sewn. Now, by Lemma 3.4, this is precisely the operation we used here construct inscribable neighborly polytopes.

**Lemma 5.4** Every Gale sewn neighborly polytope is inscribable.

As a corollary of this lemma combined with [Pad13a, Theorem 6.8], which estimates the number of Gale sewn polytopes, we obtain the following bound for inscribable neighborly $d$-polytopes with $n$ vertices. The asymptotic lower bound $n^{\frac{d}{2}n(1+o(1))}$ as $n \to \infty$ also holds when $d$ is odd, by taking pyramids (cf. [Pad13a, Corollary 6.10]).

**Theorem 5.5** For even $d$, $\mathrm{inp}(n, d)$, the number of different labeled combinatorial types of inscribable neighborly $d$-polytopes with $n$ vertices, fulfills

$$ \mathrm{inp}(n, d) \ge \prod_{i=1}^{\frac{d}{2}} \frac{(n-d-1+2i)!}{(2i)!} \\ \ge \frac{(n-1)^{\left(\frac{n-1}{2}\right)^2}}{(n-d-1)^{\left(\frac{n-d-1}{2}\right)^2} d^{\left(\frac{d}{2}\right)^2} e^{\frac{3d(n-d-1)}{4}}} \ge \left(\frac{n-1}{e^{3/2}}\right)^{\frac{1}{2}d(n-d-1)} = n^{\frac{d}{2}n(1+o(1))}. $$

## References

[Alo86] Noga Alon. The number of polytopes, configurations and real matroids. *Mathematika*, 33(1):62–71, 1986.

[BLS+93] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler. *Oriented matroids*. Encyclopedia of Mathematics and Its Applications. 46. Cambridge: Cambridge University Press. 516 p., 1993.

[Bro79] Kevin Q. Brown. Voronoi diagrams from convex hulls. *Inf. Process. Lett.*, 9:223–228, 1979.

[Car11] Constantin Carathéodory. Über den Variabilitätsbereich der Fourier’schen Konstanten von positiven harmonischen Funktionen. *Rendiconto del Circolo Matematico di Palermo*, 32:193–217, 1911.

[DRS10] Jesús A. De Loera, Jörg Rambau, and Francisco Santos. *Triangulations: Structures for algorithms and applications*, volume 25 of *Algorithms and Computation in Mathematics*. Springer-Verlag, Berlin, 2010.

[Gon13] Bernd Gonska. *Inscribable polytopes via Delaunay triangulations*. Ph.D. thesis, Freie Universität Berlin, 2013.
[GP86] Jacob E. Goodman and Richard Pollack. Upper bounds for configurations and polytopes in $R^d$. *Discrete Comput. Geom.*, 1:219–227, 1986.

[Grü03] Branko Grünbaum. *Convex polytopes*, volume 221 of *Graduate Texts in Mathematics*. Springer-Verlag, New York, second edition, 2003. Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler.

[GZ13] Bernd Gonska and Günter M. Ziegler. Inscribable stacked polytopes. *Adv. Geom.*, 13(4):723–740, 2013.

[HRS92] Craig D. Hodgson, Igor Rivin, and Warren D. Smith. A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere. *Bull. Amer. Math. Soc. (N.S.)*, 27(2):246–251, 1992.

[McM70] Peter McMullen. The maximum numbers of faces of a convex polytope. *Mathematika, Lond.*, 17:179–184, 1970.

[Pad13a] Arnau Padrol. Many neighborly polytopes and oriented matroids. *Discrete Comput. Geom.*, 50(4):865–902, 2013.

[Pad13b] Arnau Padrol. *Neighborly and almost neighborly configurations, and their duals*. Ph.D. Thesis, Universitat Politècnica de Catalunya, 2013.

[Riv96] Igor Rivin. A characterization of ideal polyhedra in hyperbolic 3-space. *Ann. of Math. (2)*, 143(1):51–70, 1996.

[Sei85] Raimund Seidel. A method for proving lower bounds for certain geometric problems. In G. T. Toussaint, editor, *Computational Geometry*, pages 319–334. North-Holland, Amsterdam, Netherlands, 1985.

[Sei87] Raimund Seidel. On the number of faces in higher-dimensional Voronoi diagrams. In *Proceedings of the third annual symposium on Computational geometry*, SCG '87, pages 181–185, New York, NY, USA, 1987. ACM.

[Sei91] Raimund Seidel. Exact upper bounds for the number of faces in $d$-dimensional Voronoi diagrams. *Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift*, 4:517–530, 1991.

[She82] Ido Shemer. Neighborly polytopes. *Isr. J. Math.*, 43:291–314, 1982.

[Ste32] Jacob Steiner. Systematische Entwicklung der Abhängigkeit geometrischer Gestalten von einander. Fincke, Berlin, 1832. Also in: Gesammelte Werke, Vol. 1, Reimer, Berlin 1881, pp. 229–458.

[Ste28] Ernst Steinitz. Über isoperimetrische Probleme bei konvexen Polyedern. *J. f. M.*, 159:133–143, 1928.

[Stu87] Bernd Sturmfels. Cyclic polytopes and $d$-order curves. *Geom. Dedicata*, 24:103–107, 1987.