Zafeirakis Zafeirakopoulos

We consider the problem of computing the topology and describing the geometry of a parametric curve in Rn. We present an algorithm, PTOPO, that constructs an abstract graph that is isotopic to the curve in the embedding space. Our method exploits the benefits of the parametric representation and does not resort to implicitization. Most importantly, we perform all computations in the parameter space and not in the implicit space. When the parametrization involves polynomials of degree at most d and maximum bitsize of coefficients τ, then the worst case bit complexity of PTOPO is O˜B(nd6+nd5τ+d4(n2+nτ)+d3(n2τ+n3)+n3d2τ). This bound matches the current record bound O˜B(d6+d5τ) for the problem of computing the topology of a plane algebraic curve given in implicit form. For plane and space curves, if N=max⁡d,τ, the complexity of PTOPO becomes O˜B(N6), which improves the state-of-the-art result, due to Alcázar and Díaz-Toca [CAGD’10], by a factor of N10. In the same time complexity, we obtain a graph whose straight-line embedding is isotopic to the curve. However, visualizing the curve on top of the abstract graph construction, increases the bound to O˜B(N7). For curves of general dimension, we can also distinguish between ordinary and non-ordinary real singularities and determine their multiplicities in the same expected complexity of PTOPO by employing the algorithm of Blasco and Pérez-Díaz [CAGD’19]. We have implemented PTOPO in maple for the case of plane and space curves. Our experiments illustrate its practical nature.

Polyhedral Omega is a new algorithm for solving linear Diophantine systems (LDS), i.e., for computing a multivariate rational function representation of the set of all non-negative integer solutions to a system of linear equations and inequalities. Polyhedral Omegacombines methods from partition analysis with methods from polyhedral geometry. In particular, we combine MacMahon’s iterative approach based on the Omega operator and explicit formulas for its evaluation with geometric tools such as Brion decompositions and Barvinok’s short rational function representations. In this way, we connect two recent branches of research that have so far remained separate, unified by the concept of symbolic cones which we introduce. The resulting LDS solver Polyhedral Omegais significantly faster than previous solvers based on partition analysis and it is competitive with state-of-the-art LDS solvers based on geometric methods. Most importantly, this synthesis of ideas makes Polyhedral Omegathe simplest algorithm for solving linear Diophantine systems available to date. Moreover, we provide an illustrated geometric interpretation of partition analysis, with the aim of making ideas from both areas accessible to readers from a wide range of backgrounds.

We investigate the arithmetic-geometric structure of the lecture hall cone \(L_n = \left\lbraceλ∈\mathbbR^n:  0≤\frac\lambda_11≤\frac\lambda_22≤\frac\lambda_33≤⋯≤\frac\lambda_nn\right\rbrace\). We show that \(L_n\)is isomorphic to the cone over the lattice pyramid of a reflexive simplex whose Ehrhart \(h^*\)-polynomial is given by the \((n-1)\)st Eulerian polynomial and prove that lecture hall cones admit regular, flag, unimodular triangulations. After explicitly describing the Hilbert basis for \(L_n\), we conclude with observations and a conjecture regarding the structure of unimodular triangulations of \(L_n\), including connections between enumerative and algebraic properties of \(L_n\)and cones over unit cubes.