  We show that a closed piecewise-linear hypersurface immersed in $R^n$ ($n\ge
3$) is the boundary of a convex body if and only if every point in the interior
of each $(n-3)$-face has a neighborhood that lies on the boundary of some
convex body; no assumptions about the hypersurface's topology are needed. We
derive this criterion from our generalization of Van Heijenoort's (1952)
theorem on locally convex hypersurfaces in $R^n$ to spherical spaces. We also
give an easy-to-implement convexity testing algorithm, which is based on our
criterion. For $R^3$ the number of arithmetic operations used by the algorithm
is at most linear in the number of vertices, while in general it is at most
linear in the number of incidences between the $(n-2)$-faces and $(n-3)$-faces.
When the dimension $n$ is not fixed and only ring arithmetic is allowed, the
algorithm still remains polynomial. Our method works in more general situations
than the convexity verification algorithms developed by Mehlhorn et al. (1996)
and Devillers et al. (1998) -- for example, our method does not require the
input surface to be orientable, nor it requires the input data to include
normal vectors to the facets that are oriented "in a coherent way". For $R^3$
the complexity of our algorithm is the same as that of previous algorithms; for
higher dimensions there seems to be no clear winner, but our approach is the
only one that easily handles inputs in which the facet normals are not known to
be coherently oriented or are not given at all. Furthermore, our method can be
extended to piecewise-polynomial surfaces of small degree.
