Evaluating the boundary and covering degree of planar Minkowski sums and other geometrical convolutions

Algorithms are developed, based on topological principles, to evaluate the boundary and “internal structure” of the Minkowski sum of two planar curves. A graph isotopic to the envelope curve is constructed by computing its characteristic points. The edges of this graph are in one-to-one correspondence with a set of monotone envelope segments. A simple formula allows a degree   to be assigned to each face defined by the graph, indicating the number of times its points are covered by the Minkowski sum. The boundary can then be identified with the set of edges that separate faces of zero and non-zero degree, and the boundary segments corresponding to these edges can be approximated to any desired geometrical accuracy. For applications that require only the Minkowski sum boundary, the algorithm minimizes geometrical computations on the “internal” envelope edges, that do not contribute to the final boundary. In other applications, this internal structure is of interest, and the algorithm provides comprehensive information on the covering degree for different regions within the Minkowski sum. Extensions of the algorithm to the computation of Minkowski sums in R³${\mathbb{R}}^3$, and other forms of geometrical convolution, are briefly discussed.     

Geometric Hermite interpolation by spatial Pythagorean-hodograph cubics

It is shown that, depending upon the orientation of the end tangents t₀,t₁ relative to the end point displacement vector p=p₁–p₀, the problem of G¹ Hermite interpolation by PH cubic segments may admit zero, one, or two distinct solutions. For cases where two interpolants exist, the bending energy may be used to select among them. In cases where no solution exists, we determine the minimal adjustment of one end tangent that permits a spatial PH cubic Hermite interpolant. The problem of assigning tangents to a sequence of points p₀,...,p_n in R³, compatible with a G¹ piecewise-PH-cubic spline interpolating those points, is also briefly addressed. The performance of these methods, in terms of overall smoothness and shape-preservation properties of the resulting curves, is illustrated by a selection of computed examples.     

Rational frames of minimal twist along space curves under specified boundary conditions

An adapted orthonormal frame (f₁(ξ),f₂(ξ),f₃(ξ)) on a space curve r(ξ), ξ ∈ [ 0, 1 ] comprises the curve tangent \(\mathbf {f}_{1}(\xi ) =\mathbf {r}^{\prime }(\xi )/|\mathbf {r}^{\prime }(\xi )|\) and two unit vectors f₂(ξ),f₃(ξ) that span the normal plane. The variation of this frame is specified by its angular velocity Ω = Ω₁f₁ + Ω₂f₂ + Ω₃f₃, and the twist of the framed curve is the integral of the component Ω₁ with respect to arc length. A minimal twist frame (MTF) has the least possible twist value, subject to prescribed initial and final orientations f₂(0),f₃(0) and f₂(1),f₃(1) of the normal–plane vectors. Employing the Euler–Rodrigues frame (ERF) — a rational adapted frame defined on spatial Pythagorean–hodograph curves — as an intermediary, an exact expression for an MTF with Ω₁ = constant is derived. However, since this involves rather complicated transcendental terms, a construction of rational MTFs is proposed by the imposition of a rational rotation on the ERF normal–plane vectors. For spatial PH quintics, it is shown that rational MTFs compatible with the boundary conditions can be constructed, with only modest deviations of Ω₁ about the mean value, by a rational quartic normal–plane rotation of the ERF. If necessary, subdivision methods can be invoked to ensure that the rational MTF is free of inflections, or to more accurately approximate a constant Ω₁. The procedure is summarized by an algorithm outline, and illustrated by a representative selection of computed examples.     

Computing the roots of sparse high–degree polynomials that arise from the study of random simplicial complexes

Numerical Algorithms - The problem of computing the roots of a particular sequence of sparse polynomials pn(t) is considered. Each instance pn(t) incorporates only the n +?1 monomial terms...     

Guaranteed consistency of surface intersections and trimmed surfaces using a coupled topology resolution and domain decomposition scheme

We describe a method that serves to simultaneously determine the topological configuration of the intersection curve of two parametric surfaces and generate compatible decompositions of their parameter domains, that are amenable to the application of existing perturbation schemes ensuring exact topological consistency of the trimmed surface representations. To illustrate this method, we begin with the simpler problem of topology resolution for a planar algebraic curve F(x,y)=0 in a given domain, and then extend concepts developed in this context to address the intersection of two tensor-product parametric surfaces p(s,t) and q(u,v) defined on (s,t)∈[0,1]² and (u,v)∈[0,1]². The algorithms assume the ability to compute, to any specified precision, the real solutions of systems of polynomial equations in at most four variables within rectangular domains, and proofs for the correctness of the algorithms under this assumption are given. Mathematics subject classification (2000)  65D17     

Solution of elementary equations in the Minkowski geometric algebra of complex sets

The solution of elementary equations in the Minkowski geometric algebra of complex sets is addressed. For given circular disks and with radii a and b, a solution of the linear equation in an unknown set exists if and only if ab. When it exists, the solution is generically the region bounded by the inner loop of a Cartesian oval (which may specialize to a limaçon of Pascal, an ellipse, a line segment, or a single point in certain degenerate cases). Furthermore, when a<b<1, the solution of the nonlinear monomial equation is shown to be the region that is bounded by a single loop of a generalized form of the ovals of Cassini. The latter result is obtained by considering the nth Minkowski root of the region bounded by the inner loop of a Cartesian oval. Preliminary consideration is also given to the problems of solving univariate polynomial equations and multivariate linear equations with complex disk coefficients.