  We show that a realization of a closed connected PL-manifold of dimension n-1
in n-dimensional Euclidean space (n>2) is the boundary of a convex polyhedron
(finite or infinite) if and only if the interior of each (n-3)-face has a
point, which has a neighborhood lying on the boundary of an n-dimensional
convex body. No initial assumptions about the topology or orientability of the
input surface are made. The theorem is derived from a refinement and
generalization of Van Heijenoort's theorem on locally convex manifolds to
spherical spaces. Our convexity criterion for PL-manifolds implies an easy
polynomial-time algorithm for checking convexity of a given PL-surface in
n-dimensional Euclidean or spherical space, n>2. The algorithm is worst case
optimal with respect to both the number of operations and the algebraic degree.
The algorithm works under significantly weaker assumptions and is easier to
implement than convexity verification algorithms suggested by Mehlhorn et al
(1996-1999), and Devillers et al.(1998). A paradigm of approximate convexity is
suggested and a simplified algorithm of smaller degree and complexity is
suggested for approximate floating point convexity verification.
