Inscribing H-Polyhedra in Quadrics using a Projective Generalization of Closed Sets

Willem Hagemann and Eike Möhlmann
Proceedings of the 27th Canadian Conference on Computational Geometry, {CCCG} 2015
We present a projective generalization of closed sets, called complete projective embeddings, which allows us to inscribe H-polyhedra in quadrics efficiently. Essentially, the complete projective embedding of a closed convex set $P \subseteq K^d$ is a double cone in $K^{d+1}$. We show that complete projective embeddings of polyhedral sets are of particular interest and already occurred in the theory of linear fractional programming. Our approach works as follows: By projective principal axis transformation the quadric is converted to a hyperboloid and then approximated by an inner (right) spherical cylinder. Now, given an inscribed H-polytope of the spherical cross section, cylindrification of the polyhedron yields an inscribed H-polyhedron of the spherical cylinder and, hence, of the hyperboloid. After application of the inverse base transformation this approach finally yields an inscribed set of the quadric. The crucial task of this procedure is to find an appropriate generalization of closed sets, which is closed under the involved projective transformations and allows us to recover the non-projective equivalents to the inscribed sets obtained by our approach. It turns out that complete projective embeddings are the requested generalizations.
Queen's University, Ontario, Canada