Discrete & Computational Geometry

Let P be a set of points in general position in the plane. Join all pairs of points in P with straight line segments. The number of segment-crossings in such a drawing, denoted by $\operatorname {cr}(P)$ , is the rectilinear crossing number of P. A halving line of P is a line passing through two points of P that divides the rest of the points of P in (almost) half. The number of halving lines of P is denoted by h(P). Similarly, a k-edge, 0≤k≤n/2−1, is a line passing through two points of P and leaving exactly k points of P on one side. The number of ≤k-edges of P is denoted by E ≤k (P). Let $\overline {\mathrm {cr}}(n)$ , h(n), and E ≤k (n) denote the minimum of $\operatorname {cr}(P)$ , the maximum of h(P), and the minimum of E ≤k (P), respectively, over all sets P of n points in general position in the plane. We show that the previously best known lower bound on E ≤k (n) is tight for k<⌈(4n−2)/9⌉ and improve it for all k≥⌈(4n−2)/9⌉. This in turn improves the lower bound on $\overline {\mathrm {cr}}(n)$ from $0.37968\binom{n}{4}+\varTheta (n^{3})$ to $\frac{277}{729}\binom{n}{4}+\varTheta (n^{3})\geq 0.37997\binom{n}{4}+\varTheta (n^{3})$ . We also give the exact values of $\overline {\mathrm {cr}}(n)$ and h(n) for all n≤27. Exact values were known only for n≤18 and odd n≤21 for the crossing number, and for n≤14 and odd n≤21 for halving lines.

We show that for every simplicial polytope an inscribed simplicial polytope exists that has the same dimension, number of vertices, number of edges, and number of 2-faces. This proves that the g-theorem for simplicial polytopes also holds for the class of inscribed simplicial polytopes (up to dimension 7). The proof includes an incremental construction scheme for Delaunay triangulations.

We consider the problem of optimality in manifold reconstruction. A random sample $$\mathbb {X}_n = \{X_1,\ldots ,X_n\}\subset \mathbb {R}^D$$ composed of points close to a d-dimensional submanifold M, with or without outliers drawn in the ambient space, is observed. Based on the tangential Delaunay complex (Discrete Comput Geom 51(1):221–267 2014), we construct an estimator $$\widehat{M}$$ that is ambient isotopic and Hausdorff-close to M with high probability. The estimator $$\widehat{M}$$ is built from existing algorithms. In a model with additive noise of small amplitude, we show that this estimator is asymptotically minimax optimal for the Hausdorff distance over a class of submanifolds satisfying a reach constraint. Therefore, even with no a priori information on the tangent spaces of M, our estimator based on Tangential Delaunay Complexes is optimal. This shows that the optimal rate of convergence can be achieved through existing algorithms. A similar result is also derived in a model with outliers. A geometric interpolation result is derived, showing that the Tangential Delaunay Complex is stable with respect to noise and perturbations of the tangent spaces. In the process, a decluttering procedure and a tangent space estimator both based on local principal component analysis (PCA) are studied.

We study line configurations in 3-space by means of “line diagrams”, projections into a plane with an indication of over and under crossing at the vertices. If we orient such a diagram, we can associate a “contracted tensor”T with it in the same spirit as is done in Knot Theory. We give conditions to makeT independent of the orientation, and invariant under isotopy. The Yang-Baxter equation is one such condition. Afterwards we restrict ourselves to Yang-Baxter invariants with a topological state model, and give some new invariants for line isotopy.

Motivated by questions in real enumerative geometry (Borcea et al., in Discrete Comput Geom 35(2):287–300, 2006; Bürgisser and Lerario, in J Reine Angew Math, https://doi.org/10.1515/crelle-2018-0009, 2018; Megyesi and Sottile, in Discrete Comput Geom 33(4):617–644, 2005; Megyesi et al., in Discrete Comput Geom 30(4):543–571, 2003; Sottile and Theobald, in Trans Am Math Soc 354(12):4815–4829, 2002; Proc Am Math Soc 133(10):2835–2844, 2005; in: Goodman et al., in Surveys on discrete and computational geometry. AMS, Providence, 2008) we investigate the problem of the number of flats simultaneously tangent to several convex hypersurfaces in real projective space from a probabilistic point of view (here by “convex hypersurfaces” we mean that these hypersurfaces are boundaries of convex sets). More precisely, we say that smooth convex hypersurfaces $$X_1, \ldots , X_{d_{k,n}}\subset {\mathbb {R}}\text {P}^n$$, where $$d_{k,n}=(k+1)(n-k)$$, are in random position if each one of them is randomly translated by elements $$g_1, \ldots , g_{{d_{k,n}}}$$ sampled independently from the orthogonal group with the uniform distribution. Denoting by $$\tau _k(X_1, \ldots , X_{d_{k,n}})$$ the average number of k-dimensional projective subspaces (k-flats) which are simultaneously tangent to all the hypersurfaces we prove that $$\begin{aligned} \tau _k(X_1, \ldots , X_{d_{k,n}})={\delta }_{k,n} \cdot \prod _{i=1}^{d_{k,n}}\frac{|\Omega _k(X_i)|}{|\text {Sch}(k,n)|}, \end{aligned}$$where $${\delta }_{k,n}$$ is the expected degree from [6] (the average number of k-flats incident to $$d_{k,n}$$ many random $$(n-k-1)$$-flats), $$|\text {Sch}(k,n)|$$ is the volume of the Special Schubert variety of k-flats meeting a fixed $$(n-k-1)$$-flat (computed in [6]) and $$|\Omega _k(X)|$$ is the volume of the manifold $$\Omega _k(X)\subset \mathbb {G}(k,n)$$ of all k-flats tangent to X. We give a formula for the evaluation of $$|\Omega _k(X)|$$ in terms of some curvature integral of the embedding $$X\hookrightarrow {\mathbb {R}}\text {P}^n$$ and we relate it with the classical notion of intrinsic volumes of a convex set: $$\begin{aligned} \frac{|\Omega _{k}(\partial C)|}{|\text {Sch}(k, n)|}=4V_{n-k-1}(C),\quad k=0, \ldots , n-1. \end{aligned}$$As a consequence we prove the universal upper bound: $$\begin{aligned} \tau _k(X_1, \ldots , X_{d_{k,n}})\le {\delta }_{k, n}\cdot 4^{d_{k,n}}. \end{aligned}$$Since the right hand side of this upper bound does not depend on the specific choice of the convex hypersurfaces, this is especially interesting because already in the case $$k=1, n=3$$ for every $$m>0$$ we can provide examples of smooth convex hypersurfaces $$X_1, \ldots , X_4$$ such that the intersection $$\Omega _1(X_1)\cap \cdots \cap \Omega _1(X_4)\subset \mathbb {G}(1,3)$$ is transverse and consists of at least m lines. Finally, we present analogous results for semialgebraic hypersurfaces (not necessarily convex) satisfying some nondegeneracy assumptions.

We show that the four-dimensional case of Graver's conjecture is not true.

With a slight modification of the original definition by Billera and Sturmfels, it is shown that the theory of fibre polytopes extends to one of mixed fibre polytopes. Indeed, there is a natural surjective homomorphism from the space of tensor weights on polytopes in a euclidean space V to the corresponding space of such weights on fibre polytopes in a subspace of V. Moreover, these homomorphisms compose in the correct way; this is in contrast to the original situation of the fibre polytope construction.

We prove a Knaster-type result for orbits of the group (Z 2) k in $S^{2^{k}-1}$ , calculating the Euler class obstruction. As a consequence, we obtain a result about inscribing skew crosspolytopes in hypersurfaces in $\mathbb{R}^{2^{k}}$ and a result about equipartition of a measures in $\mathbb{R}^{2^{k}}$ by (Z 2)k+1-symmetric convex fans.

To any generic curve in an oriented surface there corresponds an oriented chord diagram, and any oriented chord diagram may be realized by a curve in some oriented surface. The genus of an oriented chord diagram is the minimal genus of an oriented surface in which it may be realized. Let g n denote the expected genus of a randomly chosen oriented chord diagram of order n. We show that g n satisfies: $$g_n=\frac{n}{2}-\varTheta (\ln n).$$ I.e., there exist 0