Computer Science – Computational Geometry
Scientific paper
2003-09-23
Computer Science
Computational Geometry
10 pages (abbreviated version). Significantly different from all older versions. Discount the previous version -- it had many
Scientific paper
We show that a realization of a closed connected PL-manifold of dimension n-1 in n-dimensional Euclidean space (n>2) is the boundary of a convex polyhedron (finite or infinite) if and only if the interior of each (n-3)-face has a point, which has a neighborhood lying on the boundary of an n-dimensional convex body. No initial assumptions about the topology or orientability of the input surface are made. The theorem is derived from a refinement and generalization of Van Heijenoort's theorem on locally convex manifolds to spherical spaces. Our convexity criterion for PL-manifolds implies an easy polynomial-time algorithm for checking convexity of a given PL-surface in n-dimensional Euclidean or spherical space, n>2. 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 (1996-1999), and Devillers et al.(1998). A paradigm of approximate convexity is suggested and a simplified algorithm of smaller degree and complexity is suggested for approximate floating point convexity verification.
No associations
LandOfFree
Fast Verification of Convexity of Piecewise-linear Surfaces 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 Fast Verification of Convexity of Piecewise-linear Surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Verification of Convexity of Piecewise-linear Surfaces will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-182674