Narrow Results

A set of spanning line segments (SLS) is a subset of the edges of a finite polyhedron in E³ such that an arbitrary plane intersects the polyhedron if and only if the plane intersects at least one of the line segments of the SLS. In this paper an algorithm is presented for computing an almost minimum set of spanning line segments for an arbitrary polyhedron . When the number of extreme vertices of is odd, the computed SLS is minimum; when the number of extreme vertices of is even, the size of the computed SLS is at most the minimum size plus one. The algorithm has linear-time complexity for a convex polyhedron, hence is optimal in this case; its time complexity is Θ(m log m) for an arbitrary polyhedron, where m is the number of vertices of the polyhedron.

We propose a natural scheme to measure the joint separation of a cluster of objects in general geometric settings. In particular, here the measure is developed for finite sets of planes in ℝ³ in terms of extreme configurations of vectors on the planes of a given set. We prove geometric and graph-theoretic results about extreme configurations on arbitrary finite plane sets. We then specialize to the planes bounding a regular polyhedron in order to exploit the symmetries. However, even then results are non-trivial and surprising – extreme configurations on regular polyhedra may turn out to be highly irregular.

A parallel algorithm for determining the mass properties of objects represented in the Constructive Solid Geometry (CSG) scheme that uses polygons as primitives is presented. The algorithm exploits the fact that integration of local information around the vertices of the evaluated polygon is sufficient for the determination of its mass properties, i.e., determination of the edges and the complete topology of the evaluated polygon is not necessary. This reduces interprocessor communication and makes it suitable for parallel processing. The algorithm uses data parallelism, spatial partitioning and parallel sorting for parallelization. Tuple-sets on which simple operations have to be performed are identified. The elements of tuple-sets are distributed among the processors for parallelization. The uniform grid spatial partitioning technique is used to generate sub-problems that can be done in parallel and to reduce the cardinality of some of the tuple-sets generated in the algorithm. Parallel sorting is used to sort the tuple-sets between the data-parallel phases of the algorithm.

The problem of reconstructing a three-dimensional object from parallel slices has application in computer vision and medicine. Here we explore a specific existence question: given two polygons in parallel planes, is it always possible to find a polyhedron that has those polygons as faces, and whose vertices are precisely the vertices of the two polygons? We answer this question in the negative by providing an example of two polygons that cannot be connected to form a simple polyhedron. One polygon is a triangle, the other a somewhat complicated shape with spiraling pockets.

We show that the ordered rings naturally associated to compact convex polyhedra with interior satisfy a positivity property known as order unit cancellation, and obtain other general positivity results as well.