traub@cs.columbia.EDU (Joseph Traub) (10/18/90)
SPECIAL JOINT MEETING CONTINUOUS COMPUTATIONAL COMPLEXITY AND THEORY SEMINARS G.W. Wasilkowski Department of Computer Science University of Kentucky Monday, October 29th 4:10 p.m. Computer Science Conference Room 450 Computer Science Building Numerical Stability of a Convex Hull Algorithm for Simple Polygons ABSTRACT We will present a numerically stable implementation of Lee's algorithm for finding a convex hull of a simple polygon. More precisely, for simple polygons that are not ill-conditioned, the algorithm constructs an exact convex hull for slightly perturbed input points with the relative perturbations not exceeding 3 epsilon. Here epsilon is the unit round-off of the floating point arithmetic used; and by ``not ill-conditioned'' we mean that small relative perturbations of the input points do not change the original simple polygon into a polygon that is not simple. This work was done jointly with J.W. Jaromczyk.