An Efficient Local Approach to Convexity Testing of Piecewise-Linear Hypersurfaces

Abstract We prove the following criterion: a compact connected piecewise-linear hypersurface (without boundary) in R n (n ≥ 3) is the boundary of a convex body if and only if every point in the relative interior of each (n−3)-face has a neighborhood that lies on the boundary of some convex body. This criterion is derived from our theorem that any connected complete locally-convex hypersurface in S n (n ≥ 3) is the boundary of a convex body in S n . We give an easy-to-implement convexity testing algorithm based on our criterion. This algorithm does not require any assumptions about the global topology of the input hypersurface. For R 3 the number of arithmetic operations used by our algorithm is at most linear in the number of vertices, while in general it is at most linear in the number of incidences between (n − 2)-faces and (n−3)-faces. The algorithm still remains polynomial even when the dimension n is a variable and the bit complexity model for (exact) arithmetic operations is used. The suggested method works in more general situations than the convexity verification algorithms developed b