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

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

2007-03-07

arxiv.org/abs/cs/0703030v1

Computer Science

Computational Geometry

3 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

An Efficient Local Approach to Convexity Testing of Piecewise-Linear Hypersurfaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Efficient Local Approach to Convexity Testing of Piecewise-Linear Hypersurfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Efficient Local Approach to Convexity Testing of Piecewise-Linear Hypersurfaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-254595