Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!apple!agate!ucbvax!cs.columbia.EDU!traub From: traub@cs.columbia.EDU (Joseph Traub) Newsgroups: comp.theory Subject: special seminar Message-ID: Date: 17 Oct 90 18:30:23 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: Theory-B - TheoryNet Ongoing Seminars and Lectures , Joseph Traub Lines: 32 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.