Geodesic diameter of sets defined by few quadratic equations and inequalities

Abstract

We prove a bound for the geodesic diameter of a subset of the unit ball in ${\mathbb{R}}^n$ described by a fixed number of quadratic equations and inequalities, which is polynomial in $n$, whereas the known bound for general degree is exponential in $n$. Our proof uses methods borrowed from D'Acunto and Kurdyka (to deal with the geodesic diameter) and from Barvinok (to take advantage of the quadratic nature).

References in corpus (3)

• Polynomial-time computing over quadratic maps I: sampling in real algebraic sets
• Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials
• Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time