From: Jeff Erickson Newsgroups: sci.math.research Subject: Re: Smallest circle enclosing a set of points Date: Thu, 27 Aug 1998 16:42:54 -0500 Fred S Long wrote: > > Jeff Erickson wrote: > > tchow[address deleted] wrote: > > > ...find the center and radius of a smallest > > > circle enclosing all the points. > > > > It can be found in linear time using an algorithm of Welzl. > > Does this imply that a convex hull can be built in linear time? No. The smallest enclosing circle doesn't give you very much information about the convex hull! > If I recall, a convex hull using a Graham Scan was O(n log n) > because of a sort. Yes. Sorting and 2d convex hulls are equally hard. We can compute convex hulls in O(n) time after sorting the points from left to right, and we can sort a set of numbers in O(n) time after replacing each number x with the point (x,x^2) and computing the convex hull. -- Jeff Erickson jeffe@cs.uiuc.edu Computer Science Department http://www.uiuc.edu/ph/www/jeffe University of Illinois, Urbana-Champaign