|
Abstract:
We show that a PL-realization of a closed connected manifold M of dimension
n-1 in Euclidean n-space (n > 2)
is the boundary of a convex polyhedron if and
only if the interior of each (n-3)-face has
a point with an M-neighborhood
lying on the boundary of some convex body. This result is derived from our
generalization, to the spherical case, of the Van Heijenoort--A.D. Alexandrov
theorem on locally convex manifolds. No initial assumptions about the
topology or orientability of the input surface are made. Our convexity
criterion for PL-manifolds implies an easy polynomial-time algorithm for
checking convexity of a given PL-surface. 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., and Devillers, Preparata et al. In this talk I shall concentrate on
PL-surfaces and the algorithmic aspects of convexity verification, but if
time permits, I will also illustrate differences between local-to-global
convexity theorems for spherical, hyperbolic, and Euclidean spaces.
|
