# Many neighborly inscribed polytopes and Delaunay triangulations.

1 IntroductionA 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-poly topes 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].

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 [R.sup.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 Caratheodory [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, Griinbaum [Gru03] 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.sup.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.sup.[d/2]n(1+o(1))] different combinatorial types of labeled neighborly d-polytopes with n vertices (as n [right arrow] [infinity] 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.sup.[d/2]n(1+o(1))] (as n [right arrow] [infinity] 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 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] when n/d [right arrow] to (see [Alo86] and [GP86]). Hence, inscribable (neighborly) polytopes are more frequent than what one might have thought.

2 Preliminaries

Let A = {[a.sub.1], ..., [a.sub.n]} be a full dimensional point configuration in [R.sup.d] whose points are labeled by {1, ..., 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 := conv(A) [subset] [R.sup.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 conv(A) is always simplicial. A face F of a polytope P is visible from a point p if there is a point x [member of] relint(F) such that the segment [x, p] intersects P only at x. In particular, if p e 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 n 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 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.sub.i] [member of] F. The face lattice of P is then a poset of subsets of {1, ..., 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 > [d/2], which motivates the definition of neighborly polytopes as those that are |_f J -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.sub.n](d), obtained as the convex hull of n points on any d-order curve in [R.sup.d] [Stu87]. For example, the moment curve [gamma]: t [??] (t, [t.sup.2], ..., [t.sub.d]) is a d-order curve. In even dimensions, the trigonometric moment curve

[tau]: t [right arrow] (sin(t), cos(t), sin(2t), cos(2t), ..., sin([d/2]t), cos([d/2]t))

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

A triangulation of a point configuration A is a collection 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 T intersects in a common face. A triangulation T of a point configuration A [subset] [R.sup.d] is neighborly if conv(S) is a cell of T for each subset S [subset] A of size [absolute value of S] = [d + 1/2].

The Delaunay triangulation D(A) of a point configuration A [subset] [R.sup.d] in general position is the triangulation that consists of all cells defined by the empty circumsphere condition: S [member of] 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 [member of] [R.sup.d] | <x, [upsilon]> = c} defined by a normal vector v whose last coordinate is positive, a point a [member of] [R.sup.d] is said to be above (resp. below) H if <a, [upsilon]> > c (resp. <a, [upsilon]> < c).

Definition 3.1 Let A = {[[??].sub.1], ..., [a.sub.n]} be a configuration of n [greater than or equal to] d + 2 labeled points in general position in [R.sup.d].

A configuration [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of n labeled points in [R.sup.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 [less than or equal to] i [less than or equal to] n [[??].sub.i] = ([a.sub.i], [h.sub.i]) [member of] [R.sup.d+i] for some collection of heights [h.sub.i] [member of] R that fulfill:

(i) for each i [greater than or equal to] d + 2, [absolute value of [h.sub.i]] > 0 is large enough so that if [h.sub.i] > 0 (resp. [h.sub.i] < 0) then [[??].sub.i] is above (resp. below) H for every hyperplane H spanned by d +1 points of {[[??].sub.1], ..., [[??].sub.i-1]}.

(ii) for each i > d + 2, [[??].sub.i] is not contained in any of the circumspheres of any simplex spanned by d + 2 points in {[[??].sub.1], ..., [[??].sub.i-1]}.

If [h.sub.i] [greater than or equal to] 0 for every 1 [less than or equal to] i [less than or equal to] n, the lexicographic lifting is called positive.

Remark 3.2 If A is in general position, then any D-lifting [??] of A is also in general position. Furthermore, if A is in convex position, then so is [??].

We omit the proof of this easy lemma.

Lemma 3.3 For any point configuration in general position A, and for any D-lifting [??], every equatorial face of conv ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) is visible from [[??].sub.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.sup.+]93, Section 7.2] (see also [Pad13a, Section 4.1]).

Lemma 3.4 A D-lifting of A with heights h* realizes the dual oriented matroid of a lexicographic extension of the Gale dual of A\{[a.sub.n]} with signature [[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]].

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 conv(A).

Lemma 3.5 ([DRS10, Lemma 4.3.2]) Let A = {[a.sub.1], ..., [a.sub.n]} be a point configuration and let T be a triangulation of the point configuration A\[a.sub.n]. Then there is a triangulation T' of A whose cells are

T' := T [union] {conv(B [union] [a.sub.n]) | B is a face of T visible from [a.sub.n]}.

Moreover, T' is the only triangulation of A that contains all the cells of T.

Definition 3.6 The placing triangulation of A (with respect to the order induced by the labels) is the triangulation [T.sub.n] obtained iteratively as follows: [T.sub.1] is the trivial triangulation of {[a.sub.1]} and [T.sub.i] is the unique triangulation of {[a.sub.1], ..., [a.sub.1]} that contains [T.sub.i-1].

Lemma 3.7 ([DRS10, Lemma 4.3.4]) Let [??] [subset] [R.sup.d+1] be a positive D-lifting of a configuration A [subset] [R.sup.d]. Then the lower envelope of conv([??]) 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.sub.1], ..., [a.sub.n]} be a configuration of n [greater than or equal to] d + 2 labeled points in general position in [R.sup.d] and let [??] be a D-lifting of A. Then the Delaunay triangulation T := D([??]) coincides with the placing triangulation of [??].

Proof: The proof is by induction on n. If n = d +2 then both triangulations consist on the single simplex spanned by [??]. Otherwise, let T' be the Delaunay triangulation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By induction hypothesis, this is the placing triangulation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Moroever, since the lifting fulfills condition (ii), every Delaunay cell of T' is still a Delaunay cell of T. Now, by Lemma 3.5 the placing triangulation is the unique triangulation of [??] containing all the cells of T'.

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.sub.1], ..., [a.sub.n]} be a configuration of n [greater than or equal to] d + 2 labeled points in convex general position in [R.sup.d] and let [??] be a D-lifting of A. If conv(A) is k-neighborly (as a polytope), then conv([??]) is k-neighborly (as a polytope) and the placing triangulation of [??] is (k +1)-neighborly (as a triangulation).

Proof: The proof of the first claim (conv([??]) is k-neighborly) is straightforward. Indeed, since A is a projection of [??], every face of conv(A) is a projection of an equatorial face of conv([??]). In particular, since every subset of k-points of A is a face of conv(A), the corresponding points must also form an equatorial face of conv([??]).

The second claim is proved by induction on n, and it is trivial when n = d + 2. For n > d + 2, let T be the placing triangulation of [??] and T' the corresponding placing triangulation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Now fix a subset S of [??] of size k + 1. If [[??].sub.n] [not member of] S, then S forms a cell of T' by induction hypothesis, and hence of T. Otherwise, if [[??].sub.n] [member of] S, then S' = S\[[??].sub.n] must be an equatorial face of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], because conv(A) is k-neighborly. By Lemma 3.3, S' is visible from [[??].sub.n] and hence by the definition of the placing triangulation, S must be a cell of T.

The combination of these two propositions directly proves our main result.

Theorem 4.3 Let A = {[a.sub.1], ..., [a.sub.n]} be a configuration of n [greater than or equal to] d + 2 labeled points in convex general position in [R.sup.d] such that conv(A) is k-neighborly, and let [??] be a D-lifting of A. Then conv([??]) is a k- neighborly polytope with vertex set [??] 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 = vert(P) [subset] [R.sup.d], then make a D-lifting of A to obtain 'A, and finally a positive D-lifting of [??] to obtain [??]. Then conv([??]) is easily seen to be a (d + 2)-dimensional (k + l)-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.sub.1], ..., [a.sub.n]} be a configuration of n points in [R.sup.d] in general position, and let D(A) be its Delaunay triangulation. Then there is an inscribable simplicial (d + 1)-polytope [P.sub.A] with n + l vertices {[[??].sub.1], ..., [[??].sub.n], [[??].sub.n+1]} whose faces are:

(i) [??] if S is a cell of D(A) and

(ii) [[??].sub.n+1] [union] [??] if S is a face of conv(A),

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

An inscribed realization of PA 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.sub.A] of Lemma 5.1 is combinatorially equivalent to the convex hull of a positive D-lifting of A [union] {[a.sub.n+1]} for any [a.sub.n+1] [member of] [R.sup.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.sub.1], ..., [a.sub.n]} be a d-dimensional configuration of n [greater than or equal to] d + 3 points in convex general position such that conv(A) is k-neighborly, let [??] be a D-lifting of A and let [??] be a positive D-lifting of [??].

Then conv([??]) is an inscribable (k + 1)-neighborly (d + 2)-polytope. In particular, if conv(A) is neighborly, so is conv([??]).

Proof: By Proposition 4.1, the placing triangulation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] coincides with its Delaunay triangulation. Therefore, by Lemma 5.2, conv([??]) is combinatorially equivalent to the inscribed polytope [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 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 [??] is also a face of conv([??]). Since the triangulation is (k + 1)-neighborly by Proposition 4.2, then so is conv([??]).

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 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and a lexicographic extension of M[p] by q = [[p.sup.-], [a.sup.-.sub.1], ..., [a.sup.-.sub.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 poly tope 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.sup.[d/2]n(1+o(1))] as n [right arrow] [infinity] also holds when d is odd, by taking pyramids (cf. [Pad13a, Corollary 6.10]).

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

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

References

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

[BLS+93] Anders Bjorner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Gunter 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 Caratheodory. Uber den Variabilitatsbereich der Fourier'schen Konstanten von positiven harmonischen Funktionen. Rendiconto del Circolo Matematico di Palermo, 32:193217, 1911.

[DRS10] Jesus A. De Loera, Jorg Rambau, and Francisco Santos. Triangulations: Structures for algorithms and applications, volume 25 of Algorithms and Computation in Mathematics. SpringerVerlag, Berlin, 2010.

[Gon13] Bernd Gonska. Inscribable polytopes via Delaunay triangulations. Ph.D. thesis, Freie Universitat Berlin, 2013.

[GP86] Jacob E. Goodman and Richard Pollack. Upper bounds for configurations and polytopes in Rd. Discrete Comput. Geom., 1:219-227, 1986.

[GrU03] Branko GrUnbaum. 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 Gunter M. Ziegler.

[GZ13] Bernd Gonska and Gunter M. Ziegler. Inscribable stacked polytopes. Adv. Geom., 13(4):723740, 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 Politecnica 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 Abhangigkeit geometrischer Gestalten von einander. Fincke, Berlin, 1832. Also in: Gesammelte Werke, Vol. 1, Reimer, Berlin 1881, pp. 229-458.

[Ste28] Ernst Steinitz. Uber isoperimetrische Probleme bei konvexen Polyedern. J. f. M., 159:133143, 1928.

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

Bernd Gonska * and Arnau Padrol ([dagger])

Institutfur Mathematik, Freie Universitat Berlin, Germany

* Email: GonskaB@gmail.com.

([dagger]) 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".

Printer friendly Cite/link Email Feedback | |

Author: | Gonska, Bernd; Padrol, Arnau |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Date: | Jan 1, 2014 |

Words: | 3790 |

Previous Article: | Kronecker coefficients: the tensor square conjecture and unimodality. |

Next Article: | Super quasi-symmetric functions via young diagrams. |

Topics: |