Narrow Results

To calculate the Minkowski-sum based similarity measure of two convex polyhedra, many relative orientations have to be considered. These relative orientations are characterized by the fact that some faces and edges of the polyhedra are parallel. For every relative orientation of the polyhedra, the volume or mixed volume of their Minkowski sum is evaluated. From the minimum of this volume, the similarity measure is calculated. In this article two issues are addressed. First, we propose and test a method to reduce the set of relative orientations to be considered by using geometric inequalities in the slope diagrams of the polyhedra. In this way, the time complexity of O(n⁶) is reduced to O(n^4.5). Secondly, we determine which relative orientation problems are ill-posed and may be skipped because they do not maximize the similarity measure.

In an orthogonal projection of a convex polyhedron P, the visibility ratio of a face f (of an edge e) is the ratio of orthogonally projected area of f (length of e) and its actual area (length). In this paper, we give algorithms for nice projections of P such that the minimum visibility ratio among all visible faces (among all visible edges) is maximized.

In 1983 Conway and Gordon and Sachs proved that every embedding of the complete graph on six vertices, K₆, is intrinsically linked. In 2004 it was shown that all straight-edge embeddings of K₆ have either one or three linked triangle pairs. We expand this work to characterize the straight-edge embeddings of K₇ and determine the number and types of links in every embedding which forms a convex polyhedron of seven vertices.

A problem which often arises while fitting implicit polynomials to 2D and 3D data sets is the following: although the data set is simple, the fit exhibits undesired phenomena, such as loops, holes, extraneous components etc. In addition to solving this problem, it is often desired to have a "tight fit" for a data set, i.e., a polynomial with a zero set which contains the data, but as little extra area (or volume) as possible. Such "tight fits" are of special interest in robotics (for compactly describing obstacles), and in computer graphics (for ray tracing and collision detection). Previous work tackled these problems by optimizing heuristic cost functions, which penalize some of these topological problems in the fit. This paper suggests a different approach – to design parameterized families of polynomials whose zero sets are guaranteed to satisfy certain topological properties. Namely, we construct families of polynomials with zero sets which are guaranteed to contain a given convex polyhedral shape, and which are also "tight" around it. The ability to parameterize these families depends heavily on the ability to parameterize positive polynomials. To achieve this, we use some powerful recent results from real algebraic geometry.