Universality Theorems for Inscribed Polytopes and Delaunay Triangulations

摘要

We prove that every primary basic semi-algebraic set is homotopy equivalent to the set of inscribed realizations (up to Mobius transformation) of a polytope. If the semi-algebraic set is, moreover, open, it is, additionally, (up to homotopy) the retract of the realization space of some inscribed neighborly (and simplicial) polytope. We also show that all algebraic extensions of are needed to coordinatize inscribed polytopes. These statements show that inscribed polytopes exhibit the MnA v universality phenomenon. Via stereographic projections, these theorems have a direct translation to universality theorems for Delaunay subdivisions. In particular, the realizability problem for Delaunay triangulations is polynomially equivalent to the existential theory of the reals.