For a polyhedron @math P let @math B(P) denote the polytopal complex that is formed by all bounded faces of @math P. If @math P is the intersection of @math n halfspaces in @math RD, but the maximum dimension @math d of any face in @math B(P) is much smaller, we show that the combinatorial complexity of @math P cannot be too high; in particular, that it is independent of @math D. We show that the number of vertices of @math P is @math O(nd) and the total number of bounded faces of the polyhedron is @math O(nd2). For inputs in general position the number of bounded faces is @math O(nd). We show that for certain specific values of @math d and @math D, our bounds are tight. For any fixed @math d, we show how to compute the set of all vertices, how to determine the maximum dimension of a bounded face of the polyhedron, and how to compute the set of bounded faces in polynomial time, by solving a number of linear programs that is polynomial in @math n.
Our results can also be interpreted as statements about the complexity of Delaunay triangulations for inputs satisfying strong convex position assumptions. Delaunay triangulations are closely related to convex hulls: the Delaunay triangulation is combinatorially equivalent to the convex hull of a point set lifted to a sphere in one higher dimension, augmented by an extra point at the pole of the sphere, followed by the removal of all faces incident to that pole @cite_3 . If a @math -dimensional set of @math points has the property that every interior point of the convex hull of the set belongs to a Delaunay triangulation feature of dimension at least @math , then our results imply via this lifting relation that the Delaunay triangulation has @math @math -dimensional simplices. For instance, if the convex hull of a point set is a stacked polytope (a convex figure formed by gluing simplices facet-to-facet) and the Delaunay triangulation coincides with the gluing pattern of the simplices, then every interior point of the convex hull belongs either to one of the simplices or to one of the glued facets, so @math ; in this case, the number of simplices in the Delaunay triangulation is exactly @math .
@cite_3
1496278954 2029041800 2153504150 2508758617
In this paper we present several results on the expected complexity of a convex hull of @math points chosen uniformly and independently from a convex shape. (i) We show that the expected number of vertices of the convex hull of @math points, chosen uniformly and independently from a disk is @math , and @math for the case a convex polygon with @math sides. Those results are well known (see rs-udkhv-63,r-slcdn-70,ps-cgi-85 ), but we believe that the elementary proof given here are simpler and more intuitive. (ii) Let @math be a set of directions in the plane, we define a generalized notion of convexity induced by @math , which extends both rectilinear convexity and standard convexity. We prove that the expected complexity of the @math -convex hull of a set of @math points, chosen uniformly and independently from a disk, is @math , where @math is the largest angle between two consecutive vectors in @math . This result extends the known bounds for the cases of rectilinear and standard convexity. (iii) Let @math be an axis parallel hypercube in @math . We prove that the expected number of points on the boundary of the quadrant hull of a set @math of @math points, chosen uniformly and independently from @math is @math . Quadrant hull of a set of points is an extension of rectilinear convexity to higher dimensions. In particular, this number is larger than the number of maxima in @math , and is also larger than the number of points of @math that are vertices of the convex hull of @math . Those bounds are known bkst-anmsv-78 , but we believe the new proof is simpler. We give a simple combinatorial algorithm that computes a piecewise-linear approximation of a smooth surface from a finite set of sample points. The algorithm uses Voronoi vertices to remove triangles from the Delaunay triangulation. We prove the algorithm correct by showing that for densely sampled surfaces, where density depends on a local feature size function, the output is topologically valid and convergent (both pointwise and in surface normals) to the original surface. We briefly describe an implementation of the algorithm and show example outputs. The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull algorithm with the general-dimension Beneath-Beyond Algorithm. It is similar to the randomized, incremental algorithms for convex hull and delaunay triangulation. We provide empirical evidence that the algorithm runs faster when the input contains nonextreme points and that it used less memory. computational geometry algorithms have traditionally assumed that input sets are well behaved. When an algorithm is implemented with floating-point arithmetic, this assumption can lead to serous errors. We briefly describe a solution to this problem when computing the convex hull in two, three, or four dimensions. The output is a set of “thick” facets that contain all possible exact convex hulls of the input. A variation is effective in five or more dimensions. Finite convex geometries are combinatorial structures. It follows from a recent result of M. Richter and L.G. Rogers that there is an infinite set @math of planar convex polygons such that @math with respect to geometric convex hulls is a locally convex geometry and every finite convex geometry can be represented by restricting the structure of @math to a finite subset in a natural way. An @math is a differentiable convex simple closed curve @math in the plane having an inscribed circle of radius @math and a circumscribed circle of radius @math such that the ratio @math is at least @math . Motivated by Richter and Rogers' result, we construct a set @math such that (1) @math contains all points of the plane as degenerate singleton circles and all of its non-singleton members are differentiable convex simple closed planar curves; (2) @math with respect to the geometric convex hull operator is a locally convex geometry; (3) as opposed to @math , @math is closed with respect to non-degenerate affine transformations; and (4) for every (small) positive @math and for every finite convex geometry, there are continuum many pairwise affine-disjoint finite subsets @math of @math such that each @math consists of almost-circles of accuracy @math and the convex geometry in question is represented by restricting the convex hull operator to @math . The affine-disjointness of @math and @math means that, in addition to @math , even @math is disjoint from @math for every non-degenerate affine transformation @math .