Publications

This document contains a listing of some of my publications.

Papers


Envelopes of Nonlinear Geometry
Ph.D. Thesis
David Lutterkort
Paper 1999-11-09
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.
Available Formats: PDF | gzipped Postscript

Smooth paths in a polygonal channel
Extended Abstract for SCG '99 in Miami
David Lutterkort and Jörg Peters
Paper 1998-11-20
Appeared in Proceedings of the Fifteenth Annual Symposium on Computational Geometry, Miami Beach, Florida, 1999
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.
Available Formats: gzipped Postscript

Tight linear envelopes for splines
David Lutterkort and Jörg Peters
Paper 1998-11-20
To appear in Numerische Mathematik
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.
Available Formats: gzipped Postscript

Computing linear envelopes for uniform B--spline curves
Submission for SIAM Student Paper Prize
David Lutterkort
Paper 1999-02-03
Submitted to Proceedings St. Malo
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.
Available Formats: Extended Abstract (ps) | Full paper(ps)

Sharp, quantitative bounds on the distance between a polynomial piece and its Bezier control polygon
D. Nairn and J. Peters and D. Lutterkort
Paper 1998-09-01
Appeared in Computer Aided Geometric Design 16 (1999) pp. 613-631
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.
Available Formats: gzipped Postscript