An efficient local approach to convexity testing of piecewise-linear hypersurfaces (Q955229): Difference between revisions

The author discusses how the local convexity of a piecewise linear hypersurface may be used to determine its global convexity. The first half of the article centers around proving the main result (see below). The second half gives an application: a convexity checking algorithm. Apart from the proofs, the author targets a general audience familiar with notions from basic point-set and computational topology. Let \(M\) be a connected manifold of dimension \(n-1\), \({\mathcal P}\) a partition of \(M\) into semi--regular cells, and \(r:M\rightarrow{\mathbb R}^n\) a PL realization map. The author defines a point \(x\in M\) to be \textit{locally convex} if it has neighborhood whose image under \(r\) is contained in the boundary of a convex body in \({\mathbb R}^n\); \(x\) is \textit{strictly convex} if the convex body intersects a hyperplane through \(r(x)\) only at that point. The main result of the article states that \(M\) is globally convex, that is \(r\) is an embedding onto the boundary of a convex body, if certain hypotheses are satisfied, notably that \(n\geq 3\), each \(n-3\)--cell \(C\in{\mathcal P}\) is locally convex, and \(r(M)\) is bounded or has a least one point of strict local convexity. The author then uses this result to construct a convexity checking algorithm for PL hypersurfaces in dimensions \(n\geq 3\), which centers around checking convexity on \((n-3)\)--cells. Correctness of the algorithm is proved, and its computational efficiency is discussed under various computational models. The algorithm is also compared with existing ones.