a linear-time algorithm for testing the inscribability of trivalent polyhedra
We present an algorithm for testing the inscribability of a trivalent polyhedron, or, equivalently, testing the circumscribability of a simplicial polyhedron. Our algorithm runs in linear time, using only low-precision integer arithmetic. The algorithm is based on a purely combinatorial characterization of inscribable trivalent polyhedra.
algorithm test timing characterization precise