Polynomial-Time Inner Approximation