Publications

A general framework for comparing objects commonly used to represent nonlinear geometry with simpler, related objects, most notably their control polygon, is provided. The framework enables the efficient computation of bounds on the distance between the nonlinear geometry and the simpler objects and the computation of envelopes of nonlinear geometry. The framework is used to compute envelopes for univariate splines, the four point subdivision scheme, tensor product polynomials and Bezier triangles. The envelopes are used to approximate solutions to continuously constrained optimization problems.

We show how to efficiently smooth a polygon with an approximating spline that stays to one side of the polygon. We also show how to find a smooth spline path between two polygons that form a channel. Problems of this type arise in many physical motion planning tasks where not only forbidden regions have to be avoided but also a smooth traversal of the motion path is required. Both algorithms are based on a new tight and efficiently computable bound on the distance of a spline from its control polygon and employ only standard linear and quadratic programming techniques.

A sharp bound on the distance between a spline and its B-spline control polygon is derived. The bound yields a piecewise linear envelope enclosing spline and polygon. This envelope is particularly simple for uniform splines and splines in Bernstein-B\'ezier form and shrinks by a factor of~4 for each uniform subdivision step. The envelope can be easily and efficiently implemented due to its explicit and constructive nature.

We derive a new, efficiently computable bound on the distance between a uniform spline and its B--Spline control polygon in terms of the second differences of the control points. The bound is piecewise linear and sharp for quadratic and cubic splines and decreases by a factor of 4 under uniform refinement. Using this bound, we describe a simple algorithm for enveloping parametric curves.

The maximal distance between a Bezier segment and its control polygon is bounded in terms of the differences of the control point sequence and a constant that depends only on the degree of the polynomial. The constants derived here for various norms and orders of differences are the smallest possible. In particular, the bound in terms of the maximal absolute second difference of the control points is a sharp bound for the Hausdorff distance between the control polygon and the curve segment. It provides a straightforward proof of the quadratic convergence of the sequence of control polygons to the Bezier segment under subdivision or degree-fold degree-raising, and establishes the explicit convergence constants, and allows analyzing the optimal choice of the subdivision parameter for adaptive refinement of quadratic and cubic segments and yields efficient bounding regions.